I saw this method in a book, to do binary search, but I can't understand how it is working no matter how I try. Can someone explain to me exactly how it is working?

the book's explanation did not help :

The idea is to make jumps and slow the speed when we get closer to the target element. The variables k and b contain the position in the array and the jump length. If the array contains the element x , the position of x will be in the variable k after the search. The time complexity of the algorithm is O (log n ), because the code in the while loop is performed at most twice for each jump length.

what I don't get is that how is k iterating in the array? How can we make sure that it will not jump over the target's index? I tried tracing some runs of this program with sample values but couldn't figure out the pattern that k is following to find whether target x exists in the array or not.

int k = 1;
for (int b = n/2; b >= 1; b /= 2) {
while (k b <= n && t[k b] <= x) k  = b;
}
if (t[k] == x) {} // x was found at index k

note: I do understand clearly the "common binary search algorithm" (the one that uses start, middle, and end indices )

CodePudding user response：

b are the length of the jumps of your current position. As you can see, b starts as n/2 and is divided by 2 at each step up until it reaches 1.

Now, For each b, remember that b is divided by 2 at each step in the for loop, we run a while loop where we add b to to our current position, which is k. We add b to k checking for 2 conditions: k b is less than n (to make sure we don't go out of bounds), and t[k b] is less than x, which we are searching.

This effectively means that for each b, we add b to k up until where it would go over the value we are seeking. At this point, the while loop breaks and we divide b to approach slower to the target hoping we don't go over it.

The final b is just one, to make sure we don't miss x if it is just the next element after the position of k.

Look at it this way, a car is racing towards a goal. At first the car is going maximum speed, as it nears the target, it gradually decelerates up until it reaches the target.

The difference with traditional binary search, which makes it a little counter intuitive, is that in traditional binary search, we go over the target and then come back and go over again and in each iteration we decrease the steps that we take back and forth. In this algorithm, we only go forwards (never over the target), but we continuously decrease the length of the steps by dividing b.