欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法:二分查找及其变种

程序员文章站 2022-07-12 09:42:53
...
二分查找的前提条件是序列是有序的!!时间复杂度log(n).

1.正规二分查找,查找某个target

需要注意的几个地方:

  • (1) l <= h
  • (2)找到直接返回,
  • (3) 当前值 < target ,l = m +1; 当前值 > target , h = m - 1;
public int findTarget(int[] nums) {
        int l=0, h = nums.length -1;
      while(l<=h){
        int m = l + (h-l)/2;
        if(nums[m] == target)return m; //查找到,返回结果
        if(nums[m] < target){
          l =m + 1;
        }
        else{
          h = m - 1;
        }
      }
      return -1; //没找到 ,返回-1
    }

2.二分查找的延申:查找某个target的最左出现位置

需要注意的地方:

  • (1)l<h, 而不是<=
  • (2)h = m;
  • (3)return l
public int findTargetLeft(int[] nums) {
        int l=0, h = nums.length -1;
      while(l<h){
        int m = l + (h-l)/2;
        
        if(nums[m] >= target){ // 如果nums[m] == target,那么最左位置的范围就落在了[l, m]里,所以h = m,因为m也可能是最终解。
          h =m ;				//注意,当h或者l,有一个=m时,while条件必须是(l<h),而不是(l<=h),不然会进入死循环
        }
        else{
          l = m + 1;
        }
      }
      return l; //
    }
同样如果要找出现的最右位置
  • (1)l<h, 而不是<=
  • (2)l = m;
  • (3)return h
public int findTargetLeft(int[] nums) {
        int l=0, h = nums.length -1;
      while(l<h){
        int m = l + (h-l)/2;
        
        if(nums[m] <= target){
          l =m ;				
        }
        else{
          h = m - 1;
        }
      }
      return h; //
    }

3.查找大于给定元素的最小元素

给定一个有序的字符数组 letters 和一个字符 target,要求找出 letters 中大于 target 的最小字符,如果找不到就返回第 1 个字符。

Input:
letters = [“c”, “f”, “j”]
target = “d”
Output: “f”

Input:
letters = [“c”, “f”, “j”]
target = “k”
Output: “c”

public char nextGreatestLetter(char[] letters, char target) {
    int n = letters.length;
    int l = 0, h = n - 1;
    while (l <= h) {
        int m = l + (h - l) / 2;
        if (letters[m] <= target) {
            l = m + 1;
        } else {
            h = m - 1;
        }
    }
    return l < n ? letters[l] : letters[0];
}

4.一个有序数组只有一个数不出现两次,找出这个数。

  • 要求以 O(logN) 时间复杂度进行求解,因此不能遍历数组并进行异或操作来求解,这么做的时间复杂度为 O(N)。

  • 令 index 为 Single Element 在数组中的位置。在 index 之后,数组中原来存在的成对状态被改变。如果 m 为偶数,并且 m + 1 < index,那么 nums[m] == nums[m + 1];m + 1 >= index,那么 nums[m] != nums[m + 1]。

  • 从上面的规律可以知道,如果 nums[m] == nums[m + 1],那么 index 所在的数组位置为 [m + 2, h],此时令 l = m + 2;如果 nums[m] != nums[m + 1],那么 index 所在的数组位置为 [l, m],此时令 h = m。

  • 因为 h 的赋值表达式为 h = m,那么循环条件也就只能使用 l < h 这种形式。

public int singleNonDuplicate(int[] nums) {
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int m = l + (h - l) / 2;
        if (m % 2 == 1) {
            m--;   // 保证 l/h/m 都在偶数位,使得查找区间大小一直都是奇数
        }
        if (nums[m] == nums[m + 1]) {
            l = m + 2;
        } else {
            h = m;
        }
    }
    return nums[l];
}

5.查找第一个错误的版本

题目描述:给定一个元素 n 代表有 [1, 2, …, n] 版本,在第 x 位置开始出现错误版本,导致后面的版本都错误。可以调用 isBadVersion(int x) 知道某个版本是否错误,要求找到第一个错误的版本。

  • 如果第 m 个版本出错,则表示第一个错误的版本在 [l, m] 之间,令 h = m;否则第一个错误的版本在 [m + 1, h] 之间,令 l = m + 1。

  • 因为 h 的赋值表达式为 h = m,因此循环条件为 l < h。

//即 在[true,true,true,false,false,false,..]数组里面寻找false的最左下标
public int firstBadVersion(int n) {
    int l = 1, h = n;
    while (l < h) {
        int mid = l + (h - l) / 2;
        if (!isBadVersion(mid)) {
            h = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

6.旋转最小数字

Input: [3,4,5,1,2],
Output: 1

// 即 寻找最小数的最左下标
public int findMin(int[] nums) {
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int m = l + (h - l) / 2;
        if (nums[m] <= nums[h]) { //
            h = m;
        } else {
            l = m + 1;
        }
    }
    return nums[l]; //attention
}
同理,如果要寻找旋转最大数字,则变成了寻找最右下标
public int findMin(int[] nums) {
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int m = l + (h - l) / 2;
        if (nums[m] >= nums[h]) { //
            l = m;
        } else {
            h = m - 1;
        }
    }
    return nums[h];
}