Is it possible to have only one comparison per iteration of the binary search algorithm?

Question

In the binary search algorithm, we have two comparisons:

if (key == a[mid]) then found; else if (key < a[mid]) then binary_search(a[],left,mid-1); else binary_search(a[],mid+1,right); 

Is there a way by which I can only have one comparison instead of the ones above.

-

thanks

Alok.Kr.

Answer 1

Cm:

http://en.wikipedia.org/wiki/Binary_search_algorithm#Single_comparison_per_iteration

Taken from the wiki:

  low = 0 high = N while (low < high) { mid = low + ((high - low) / 2) if (A[mid] < value) low = mid + 1; else //can't be high = mid-1: here A[mid] >= value, //so high can't be < mid if A[mid] == value high = mid; } // high == low, using high or low depends on taste if ((low < N) && (A[low] == value)) return low // found else return -1 // not found 

Pros / cons of the wiki: “This approach makes it possible to finish early when a match is found, so successful searches have iterations log2 (N) instead of the expected iterations log2 (N) -1. On the other hand, this implementation makes fewer comparisons: log2 (N) less than the expected number of comparisons for two test implementations 1 · 5 (log2 (N) - 1), for N more than eight. "

Answer 2

Yes. Just don't remove mid from the recursive call.

 if ( left == right ) return NULL; if ( left + 1 == right ) return key == a[left]? &a[left] : NULL; mid = left + ( right - left / 2 ); if (key < a[mid]) return binary_search(a[],left,mid-1); else return binary_search(a[],mid,right); // include `mid` in next round 

You only need to eliminate half the set with each recursion to achieve O (logN) performance. You go higher and higher, eliminating half + 1.

If you use only < during recursion, the algorithm will find the smallest element that is not less than key (but can be more than key ). Complete the execution by running one equality test.

Answer 3

In assembler you can:

 cmp key,a[mid] beq found bge else 

So, if your compiler is really good at optimizing your signature, it may already do this for you.

Answer 4

This is a recursive algorithm. The first comparison is the stopping criteria and the second actual search, so you cannot delete them.

First, you ask when you have already found the element, and in the second, in which part of the array to search for the element. Therefore, you cannot make these decisions on just one comparison.

Answer 5

First of all, is it necessary to optimize the program? Have you appreciated where you need to do this? Is it in this function?

For primitive types, the second comparison is as fast as it gets. A higher comparison cost is to load an element in the appropriate register and this is necessary for the first comparison. Once this comparison is performed, the value is already in the register, and the second operation accepts an instruction with one processor plus the possible cost of incorrect branch prediction.

Assuming integral types, the cost of the processor time of the algorithm is most likely determined in many ways by the cost of recursive calls if the compiler cannot perform tail recursion optimization. If you really need to optimize this, try compiling with all the optimization flags and analyze the assembler to determine if tail recursion optimization is being applied. If not, manually convert the algorithm from recursive to iterative.

This will have two effects: overshadow the code (avoid modifying a clean solution if you really need it), and avoid function calls.

If you are talking about C ++, and the type is complex, and the overloaded comparison operators are expensive, then the fastest performance growth is the compare method, which will return a negative number less than 0 for an equal and positive number, if more than. Then pre-compare the result before the comparison, and then perform integer checks. This will reduce the total cost of the algorithm to a single processing of real objects using expensive comparisons and return you to the original assumption.

Answer 6

 for (step = 0; step < n; step <<= 1); for (i = 0; step; step >>= 1) if (i + step < n && v[i + step] <= x) i += step; 

Answer 7

Well, that was an interview question in Adobe, and I was just trying to figure out how to do this.

Now I have a solution, so I, m send

 void binary_search (int a[] , int low , int high , int key ) { int mid = (low+high)/2; if (key == a[mid]) { printf ("Number Found\n"); return; } else { int sign = Calc_sign (key-a[mid]); low = low*sign + (1-sign)*mid; high = mid*sign + (1-sign)*right; binary_search (a,low,high,key); } } int Calc_sign(int a) { return ( (a & 80000000) >> 31); } 

Thus, there will be only one comparison in the code to check whether the key value of eqaul is the middle element.

-

thanks

Alok Kr.