I recently found this contest on a blog I follow » Are you one of the 10% of programmers who can write a binary search? I was immediately challenged by this and this is my attempt at doing a binary-search O(log2(n) function.
#include <stdio.h>
#include <string.h>
#define a1 { 1, 7, 11, 15, 22, 27, 89, 103 }
int mybsearch(int* v, int k, int len) {
int i, pos, test, min, max;
for (i = 0, min = 0, max = len-1; i < len; i++) {
pos = ((max-min)/2) + min;
test = v[pos];
if (k <= test) {
if (k == test)
return pos;
else {
max = pos;
}
}
else {
min = pos + 1;
}
}
return -1;
}
int main(int argc, char** argv) {
int query = atoi(argv[1]);
int pos;
int v[] = a1;
if ((pos = mybsearch(v, query, 0)) < 0)
printf("%d not found in array\n", query);
else
printf("%d found in position %d\n", query, pos);
return 0;
}
This was supposed to be without any testing. Meaning, you could compile but no debugging until you said » done! I had to compile 3 times and 25 minutes, or so, later, there it was. Working and passing all tests I tried:
1. Empty array
2. First position key-value
3. Last position key-value
4. Even and odd array sizes
This piece of code doesn't check many possible errors on input, etc. What matters is the mybsearch function.