Let’s assume that there are only 10 orders, and the order amounts are: 8,11,19,23,27,33,45,55,67,98. Now we need to find the order with the order amount of 19. The search process is as follows:After reading the above example, summarize what binary search is:Binary search is for an ordered set of data, and the search idea is kind of like the dive-and-conquer idea. Each time, by comparing the middle element of the interval, the interval to be searched is reduced by half until the element to be searched is found, or the interval is reduced to 0.

We’re going to assume that the size of the data is n, and every time we look it up it’s going to shrink by half, so it’s going to divide by 2. In the worst case, it does not stop until the search interval is narrowed to empty.As you can see, this is a geometric sequence. Where n/2k=1, the value of k is the total reduction. Each reduction operation only involves size comparison of two data. Therefore, after k interval reduction operations, the time complexity is O(k). And by n over 2k is equal to 1, we know that k is equal to log base n, so the time complexity is order log base n.

According to the above description, let’s implement binary search:

public int bsearch(int[] a,int n, int target) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid = low + ((high - low) >> 1);
    if(a[mid] < target) {
      low = mid + 1;
    } else if (a[mid] > target) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}
Copy the code

Here are three things that could go wrong:

  1. Loop exit condition: Note low<=high, not low
  2. The value of mid: actually, mid is equal to (low+high)/2, which is a problem. Because if the low and the high are big, the sum of them might overflow. The improved method is to write mid as low+(high-low)/2. Further, if we want to optimize the performance to the utmost, we can convert the divide by 2 operation here to low+((high-low)>>1). Because computers can handle bit operations much faster than division.

3. Update: low=mid+1, high=mid-1. And notice that this plus 1 and minus 1, if I just wrote low=mid or high=mid, it would be an infinite loop. For example, when high=3 and low=3, if a[3] is not equal to value, the loop will not exit.

Four kinds of binary search deformation:

  1. Finds the first element whose value is equal to the given value
public int bsearch(int[] a,int n,int target) { int low = 0; int high = n - 1; while(low <= high) { int mid = low + ((high - low) >> 1); if(a[mid] < target) { low = mid + 1; } else if(a[mid] > target) { high = mid - 1; } else { if(mid == 0 || (a[mid] ! = a[mid - 1])) return mid; else high = mid - 1; }}}Copy the code
  1. Finds the element whose last value is equal to the given value
public int bsearch(int[] a,int n,int target) { int low = 0; int high = n - 1; while(low <= high) { int mid = low + ((high - low) >> 1); if(a[mid] < target) { low = mid + 1; } else if(a[mid] > target) { high = mid - 1; } else { if(mid == 0 || (a[mid] ! = a[mid + 1])) return mid; else low = mid + 1; }}}Copy the code
  1. Finds the first element that is greater than or equal to the given value
public int bsearch(int[] a,int n,int target) { int low = 0; int high = n - 1; while(low <= high) { int mid = low + ((high - low) >> 1); if(a[mid] < target) { low = mid + 1; } else if(a[mid] >= target) { if(mid == 0 || (a[mid - 1] < target)) return mid; else high = mid - 1; }}}Copy the code
  1. Finds the last element that is less than or equal to the given value
public int bsearch(int[] a,int n,int target) { int low = 0; int high = n - 1; while(low <= high) { int mid = low + ((high - low) >> 1); if(a[mid] > target) { high = mid - 1; } else { if((mid == high) || (a[mid + 1] > target)) return mid; else low = mid + 1; }}}Copy the code