April 19, 2010 22:30 · Apr 19, 2010
diff --git a/binary search on queue b/binary search on queue
@@ -0,0 +1,111 @@
+/*
+        Binary search on a queue. Complexity approaches 2*N (I think).
+        Worse than linear search. I feel dirty now.
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+struct item {
+        struct item *next;
+        int mark;
+        int x;
+};
+
+struct item *
+make_list (int i, int x, int y)
+{
+        struct item *it = malloc(sizeof(struct item));
+
+        it->mark = 0;
+
+        if (0 == i) {
+                it->next = NULL;
+                it->x = x + y;
+        } else {
+                it->next = make_list(i - 1, y, x + y);
+                it->x = x + y;
+        }
+
+        return it;
+}
+
+void
+print_list (struct item *it)
+{
+        printf("%07d%c", it->x, it->mark ? '!' : ' ');
+
+        if (NULL != it->next) {
+                print_list(it->next);
+        }
+}
+
+/* Use of goto instead of recursion, just to make it extra painful. */
+
+void
+search_list (const int g, struct item *start)
+{
+        struct item *lo = start, *hi, *slow = start, *fast = start;
+        int ab = 1;
+
+        while (NULL != fast->next) {
+                fast = fast->next;
+                if (ab ^= 1) {
+                        slow = slow->next;
+                }
+        }
+
+        if (slow->x >= g) {
+                lo = start;
+                hi = slow;
+        } else {
+                lo = slow;
+                hi = fast;
+        }
+
+down:
+        if (slow->next == fast) {
+                goto end;
+        }
+
+        ab = 1;
+        slow = fast = lo;
+        while (hi != fast) {
+                fast = fast->next;
+                if (ab ^= 1) {
+                        slow = slow->next;
+                }
+        }
+
+        if (slow->x >= g) {
+                hi = slow;
+        } else {
+                lo = slow;
+                hi = fast;
+        }
+
+        goto down;
+
+
+end:
+        if (slow->x == g) {
+                slow->mark = 1;
+        }
+
+        if (fast->x == g) {
+                fast->mark = 1;
+        }
+}
+
+int
+main (void)
+{
+        struct item *it = make_list(29, 0, 1);
+
+        print_list(it);
+        printf("\nsearch for 610 ...\n");
+        search_list(610, it);
+        print_list(it);
+
+        return EXIT_SUCCESS;
+}