Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/*
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment