原理

image.png

实现

递归实现

  1. private static int binarySearch2(int[] arr,int begin,int end, int r){
  2.     if(arr.length<=0 || begin==end) {
  3.       return -1;
  4.     }
  6.     //避免整数溢出
  7.     int mid = begin + ((end-begin)>>1);
  9.     if(r== arr[mid]){ return mid; }
  11.     if(r> arr[mid]){
  12.       return binarySearch2(arr,mid+1, end,r);
  13.     }else{
  14.       return binarySearch2(arr,begin,mid-1,r);
  15.     }
  17.   }

循环实现

  1. private static int binarySearch3(int[] arr, int r){
  2.     if(arr == null || arr.length<=0) {
  3.       return -1;
  4.     }
  5.     int begin = 0;
  6.     int end = arr.length;
  8.     while (end>begin){
  10.       int mid = begin + ((end-begin)>>1);
  11.       if(arr[mid] ==r){
  12.         return mid;
  13.       }
  15.       if(arr[mid] > r){
  16.         end = mid-1;
  17.       }else{
  18.         begin = mid+1;
  19.       }
  20.     }
  21.     return -1;

存在的问题

当存在多个重复值时，查询的结果返回不稳定