• 前提条件：队列是有序的
  • 不计算排序时间的话时间复杂度是O(logn),计算排序时间的话复杂度变为O(nlogn)
  • 应用：多次查找

递归实现二分查找法

  1.     public static <E extends Comparable<E>> int  search(E[] data,E target){
  2.         return search(data,0, data.length,target);
  3.     }
  5.     private static <E extends Comparable<E>> int search(E[] data,int l ,int r, E target){
  6.         if (l>r) return -1;
  8.         int mid = l+(r-l)/2;
  10.         if (data[mid].compareTo(target) == 0) return mid;
  12.         if (data[mid].compareTo(target) < 0){
  13.             search(data,mid+1,r,target);
  14.         }
  15.         return search(data,0,mid-1,target);  //if (data[mid].compareTo(target) > 0)
  16.     }

非递归实现二分查找法

  1.     public static <E extends Comparable<E>> int  searchR(E[] data,E target){
  3.         int l = 0, r = data.length-1;
  5.         while (l <=r ){
  6.             int mid = l+(r-l)/2;
  7.             if (data[mid].compareTo(target) == 0)
  8.                 return mid;
  9.             else if (data[mid].compareTo(target) < 0 )
  10.                 l = mid+1;
  11.             else
  12.                 r = mid-1;
  13.         }
  15.         return -1;
  16.     }

修改循环不变量的定义之后

  • 定义：在[l,r)的范围里面查找target

    • 首先左边界L原来是data.length-1，现在应该是data.length

      1. public static <E extends Comparable<E>> int searchR2(E[] data,E target){
      3.    int l = 0, r = data.length;
      5.    while (l < r ){
      6.        int mid = l+(r-l)/2;
      7.        if (data[mid].compareTo(target) == 0)
      8.            return mid;
      9.        else if (data[mid].compareTo(target) < 0 )
      10.            l = mid+1; //继续在data[mid+1,r)范围里寻找解
      11.        else
      12.            r = mid ; //继续在data[l,mid)范围里寻找解
      13.    }
      15.    return -1;
      16. }

二分查找法的变种

查找大于target的最小值

  • 关键部分的代码:

    1. if(arr[mid] > target) r = mid
    2. if(arr[mid] < target) l = mid + 1
    1.   public static <E extends Comparable<E>> int upper(E[] data,E target){
    3.       int l = 0, r = data.length;
    5.       while (l < r ){
    6.           int mid = l+(r-l)/2;
    7.            if (data[mid].compareTo(target) <= 0 )
    8.               l = mid+1;
    9.           else
    10.               r = mid ; // 之所以r != mid -1 是因为该target可能就是最小值
    11.       }
    13.       return l;
    14.   }

  • 举一个例子

二分查找法 - 图1

另一个变种ceil

  • 定义

    • 如果数组中存在元素，返回最大索引

    • 如果数组中不存在元素，返回upper

      1. public static <E extends Comparable<E>> int ceil(E[] data,E target){
      3.    int u = upper(data,target);
      4.    if ((u-1) >= 0 && data[u-1].compareTo(target)==0 ){
      5.        return u-1; //返回最大索引
      6.    }
      7.    return u;
      8. }

      lower_ceil

  • 定义(>=target的最小索引)

    • 如果数组中存在元素，返回最小索引
    • 如果数组中不存在元素，返回upper ```java public static > int lower_ceil(E[] data,E target){
  1.     int l = 0, r = data.length;
  3.     while (l < r ){
  4.         int mid = l+(r-l)/2;
  5.         if (data[mid].compareTo(target) < 0 )
  6.             l = mid+1;
  7.         else
  8.             r = mid ;
  9.     }
  11.     return l;
  12. }
  1. <a name="kOHUw"></a>
  2. ## lower
  4. - 查找小于target的最大值
  5. ```java
  6.    public static <E extends Comparable<E>> int lower(E[] data,E target){
  8.         int l = -1, r = data.length-1;
  10.         while (l < r ){
  11.             int mid = l+(r-l+1)/2; //需要向上取整(大坑)
  12.             if (data[mid].compareTo(target) < 0 )
  13.                 l = mid;
  14.             else
  15.                 r = mid-1 ;
  16.         }
  18.         return l;
  19.     }

作业

  • Select K 在arr[l,r)的范围中寻找k小元素
  • 归并排序