Rock Hymas

In my last post I mentioned that I was doing some practice with the binary search algorithm. I wanted to approach it with a slightly different mindset and see what kind of an algorithm that led to. So I decided to think of it as a walk. I would go “visit” locations in the array and see if I should turn right or left at each one. Doing this in C meant that I could do some crazy stuff with arrays - nothing I would do in shipping code, but fun to play with nevertheless. Here is what I came up with:

 1 char ChopWalk(int value, int *array, int size, int *poffset)
 2 {
 3     int walkto = size / 2;
 4     int direction = 0;
 5     char found = 0;
 6 
 7     if (walkto == size)
 8         return 0;
 9 
10     if (value == array[walkto])
11     {
12         found = 1;
13         direction = 0;
14     }
15     else
16     {
17         if (value > array[walkto])
18             direction = +1;
19         else if (value < array[walkto])
20             direction = -1;
21         found = ChopWalk(value, &array[walkto + direction], direction * (size / 2), poffset);
22     }
23 
24     *poffset += walkto + direction;
25 
26     return found;
27 }
28 
29 int Chop(int value, int *array, int size)
30 {
31     int result = 0;
32     if (ChopWalk(value, array, size, &result))
33         return result;
34     else
35         return -1;
36 }