A problem in many binary search implementations?

We know that the binary search algorithm is better than the linear search algorithm. The time required to execute this algorithm is O(log n). Most of the time though, there are some issues with the implemented code. Let us consider a binary search algorithm function as shown below −

Example

int binarySearch(int array[], int start, int end, int key){
   if(start <= end){
      int mid = (start + end) /2); //mid location of the list
      if(array[mid] == key)
         return mid;
      if(array[mid] > key)
         return binarySearch(array, start, mid-1, key);
         return binarySearch(array, mid+1, end, key);
   }
   return -1;
}

This algorithm works fine until it reaches a larger number at the beginning and end. If (start end) exceeds the value 2³² - 1, a negative number may be returned after wrapping. Since negative numbers are not supported as array indices, this may cause some problems.

To solve this problem, there are a few different ways.

Method 1

int mid = start + ((end - start) / 2)

The second method only works in Java because C or C++ doesn't have the >>> operator.

Method 2 (Java only)

int mid = (start + end) >>> 1

Since C or C++ does not support >>>, we can use the following method.

Method 3

int mid = ((unsigned int) low + (unsigned int) high) >> 1

The above is the detailed content of A problem in many binary search implementations?. For more information, please follow other related articles on the PHP Chinese website!