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

2024-01-03 12:37:51

二分查找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;
      }
      

文章来源:https://blog.csdn.net/bfbshs_ddd/article/details/135358445
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。