数据结构与算法之二分查找

二分查找Binary Search

Binary Search：一种针对有序区间内时间复杂度为O(logN)的搜索方式，最常见用于已经排好序的数组

典例：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left=0,right=nums.length-1;

    while(left<=right){
        //避免整数溢出,java 可以直接向下取整，js需要使用Math.floor()
        mid =Math.floor( left+(right-left)/2);
        if(nums[mid]<target){
            left=mid+1;
        }else if(nums[mid]>target){
            right = mid-1;
        }else{
            return mid;
        }

    }
    return -1;
};

两大基本原则

边界处理不当，可能会导致跳过需要的结果或者死循环

1. 每次都要缩减搜索区域
2. 每次缩减不能排除潜在答案

三大模板

• 找一个准确值

  • 循环条件：l<=r
  • 缩减搜索空间：l=mid+1|r=mid-1

• 找一个模糊值（如比x大的最小数）

  • 循环条件：l<r
  • 缩减搜索空间：l=mid|r=mid-1或l=mid+1|r=mid

• 万用型

  • 循环条件l<r-1
  • 缩减搜索空间：l=mid|r=mid

实践应用

1. 例题

• 找一个模糊值

  循环条件：l<r

  缩减搜索空间：l=mid|r=mid-1或l=mid+1|r=mid

  1. first occurance of k

     这里选择l=mid+1|r=mid，因为最后还需要向左搜索移动r，但r=mid可能为解需要保留

     代码如下：

     public int binarySearch(int[] arr,int k){
      int l=0,r=arr.length-1;
      while(l<r){
          int mid=l+(r-l)/2;
          //avoid overflow ,L+R是否超过int的范围不确定,可能overflow,但r-l一定不溢出
          if (arr[mid]<k){
              l=mid+1;
          }else{
              r=mid
          }
      }
      return l;
      //l=r at last
     }
     

  2. last occurance of k

     这里选择l=mid|r=mid-1，因为最后还需要向右搜索移动l，但l=mid可能为解需要保留

     代码如下：

     public int binarySearch(int[] arr,int k){
      int l=0,r=arr.length-1;
      while(l<r){
          int mid=l+(r-l+1)/2;
          //避免2个元素mid停在左侧无法缩减搜索空间
          if(arr[mid]>k){
              r=mid-1;
          }else{
              l=mid
          }
      }
      return l;
     }
     

  3. closest to k

     l=mid|r=mid

     代码如下：

     public int binarySearch(int[] arr,int k){
      int l=0,r=arr.length-1;
      //搜索空间减小到2就停止，即l,r相邻
      while(l<r-1){
          int mid=l+(r-l)/2;
          if(arr[mid]<k){
              l=mid;
          }else{
              r=mid;
          }
      }
      if(arr[l]>k){
          return l;
      }else if(arr[r]<k){
          return r;
      }else{
          //成立则取“：”左侧值，否则取右侧值
          return k-arr[l]<arr[r]-k?l:r;
      }
     }
     

• 力扣1062.最长重复子串

  • 构造函数f(x)，判断长度x能否为解

  • 重复意味着子串最少出现两次，且该子串长度最大为n-1，二分查找（l=0,r=n-1,l<r）

    • mid=l+(r-l+1)/2
    • case1:f(mid) =true,l=mid
    • case2:f(mid)=false,r=mid-1

    public int LRS(String s){
        int l=0,r=s.length()-1;
        while(l<r){
            int mid = l+(r-l+1)/2;
            if(f(s,mid)){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        return l;
    }
    
    public boolean f(String s,int length){
        Set<String> seen=new HashSet<>();
        for(int i=0;i<=s.length()-length;i++){
            int j=i+length-1;
            String sub =s.substring(i,j+1);
            if(seen.contains(sub)){
                return true;
            }
            seen.add(sub);
        }
        return false;
    }