[数据结构与算法]数组下标二分算法总结

二分算法

引言：
假如给定一个有序数组，要求在该数组中查找相应的数字，如果是使用一重循环进行遍历数组的话，改时间复杂度是O(n),如果是使用二分搜索算法的，能进行一些优化在时间复杂度方面，时间复杂度为O(logn)。

1.算法思想：

设定两个指针，一个是左指针，还有一个是右指针，左指针指向数组头部，右指针指向数组尾部（当然这是根据题目的意思进行设置的，在我所举的例子中这样设定）,然后进行取中间值进行判断比较，进而缩小查找的范围。

注意点：

二分算法最难的是边界情况的处理，如果没有处理好就会导致二分算法不能正确解决相应的问题。下面就由我来介绍几种框架给大家

2.第一种

寻找某一个数的二分：

int l = 0, r = nums.length - 1;
 while(l <= r){
      int mid = (l + r) / 2;
      if(nums[mid] == target){
          return mid;
      }else if(nums[mid] < target){
          l = mid + 1;
      }else if(nums[mid] > target){
          r = mid - 1;
      }
  }
  return -1;

对该框架进行解释：

1. 为什么是l <= r？

因为我们这里的 r是这个数组的最后一个元素的下标值（r = nums.length - 1），所以我们这里使用l <= r，如哦你自己愿意的话，也可以对其进行修改，但建议不要进行修改，因为这里的框架和后面的统一，进而好记，且后面的框架的最后的返回值还有一定的含义，所以还是跟着我一起记住这一个框架吧。

2. 为什么是l = mid + 1?

因为进入该循环的条件是nums[mid] < target，并且数组有序，所以该l = mid + 1（即l向右移动缩小搜索范围），同理可得r = mid - 1。

3.就是int mid = (l + r) / 2的处理

如果题目所给的数组长度过大可能会导致mid爆int，所以我们可以做出以下处理：int mid = l + (r - l) / 2

看到这里，恭喜各位基本掌握第一个框架。

3.第二种

右边界：
直接上代码：

int l = 0, r = letters.length - 1;
while(l <= r){
    int mid = (l + r) / 2;
    if(letters[mid] == target){
        l = mid + 1;
    }else if(letters[mid] < target){
        l = mid + 1;
    }else if(letters[mid] > target){
        r = mid - 1;
    }
}
if(r < 0 || letters[r] != target) return -1;
return r;

对该框架进行解释：

上一个框架解释过的在这里就不再过多述说了

1.为什么当==时，l = mid + 1?

因为这个框架要查找的是值为target，并且是最右边的那个的下标，所以当相等的时候也要往右边靠，所以就是l = mid + 1。

2.为什么最后还要加一个这样的判断？

因为最后循环结束的时候是l = r + 1，而这里的l可以等于0，所以最后r可能小于0，所以需要进行判断，当然是不存在相应的target。而且还要判断该值是否等于target。

3.当然这里的返回的r的含义

右边界法：如果存在该数则返回的是 该数的最右边的一个的下标，如果不存在该数则返回的是 小于该数的第一个数的下标值。

4.第三种

左边界
直接上代码：

public int left_bound(int[] num,int target1){
   int l = 0, r = num.length - 1;
   while(l <= r){
       int mid = l + (r - l) / 2;
       if(num[mid] == target1){
           r = mid - 1;
       }else if(num[mid] < target1){
           l = mid + 1;
       }else if(num[mid] > target1){
           r = mid - 1;
       }
   }
   if(l == num.length || num[l] != target) return -1;
   
   return l;
}

对该框架进行解释：

1.为什么当==时，r = mid - 1?

因为这个框架要查找的是值为target，并且是最左边的那个的下标，所以当相等的时候也要往左边靠，所以就是r = mid - 1。

2.为什么最后还要加一个这样的判断？

因为最后循环结束的时候是l = r + 1，而这里的r可以等于num.length - 1，所以最后l可能等于num.length，所以需要进行判断，当然是不存在相应的target。而且还要判断该值是否等于target。

3.当然这里的返回的l的含义

左边界法：如果存在该数则返回的是 该数的最左边的一个的下标，如果不存在该数则返回的是 小于该数的个数。

5.相应的leetcode题目

1.寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题

样例：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。

AC代码：

相关解说：该方法被寓意为爬坡法，因为需要找到任意一个峰值，所以，我们可以这样做出选择，那么选择是哪一个峰值取决于第一个中值相对应的左还是右的选取

class Solution {
    public int findPeakElement(int[] nums) { 
        int l = 0, r = nums.length - 1;
        while(l < r){
            int mid = (l + r) >> 1;
            if(nums[mid] < nums[mid + 1]){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return l;
    }
}

上坡阶段： mid + 1 可能是峰值，所以 l = mid + 1;

if(nums[mid] < nums[mid + 1]){
    l = mid + 1;
}

此时也是上坡阶段：mid 也可能是峰值，所以 r = mid;

else{
  r = mid;
}

2.两数之和

给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

样例：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

输入：numbers = [2,3,4], target = 6
输出：[1,3]

输入：numbers = [-1,0], target = -1
输出：[1,2]

AC代码：

相关解说：两个数之和为一个定值，可以使用二分搜索，先遍历第一个值，然后二分搜索第二个值。使用的是第一个框架。最快的是双指针算法。

for(int i = 0; i < numbers.length; i ++){
    int target1 = target - numbers[i];

    int l = i + 1, r = numbers.length - 1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(numbers[mid] == target1){
            return new int[]{i + 1,mid + 1};
        }else if(numbers[mid] < target1){
            l = mid + 1;
        }else if(numbers[mid] > target1){
            r = mid - 1;
        }
    }
   
}
return new int[]{-1,-1};

3.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

样例：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

输入：target = 4, nums = [1,4,4]
输出：1

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

AC代码：

相关解说：该题本来是求多个变量的和再进行比较，然而通过前缀和进行优化转化为了求两个 相应的前缀和数组的值的差为一个定值，那么就可以这样先确定一个数组值，然后通过加减先求出对应的值，再进行二分搜索查找到相应的值的下标

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        if(nums.length == 0) return 0;

        int[] sum = new int[nums.length + 1];

        
        for(int i = 1; i <= nums.length; i ++){
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        int res = Integer.MAX_VALUE;

        //其实这是对暴力做法的优化，暴力做法是 两数相减 第二重循环是起到寻找第二个数的作用，
        // 那么我们可以先将target 和 所作为左端点的值相加去寻找右端点，进而起到优化第二重循环的作用
        // 类似于 题目：两数之和II (167题)
        for(int i = 1; i <= nums.length; i ++){
            int target1 = target + sum[i - 1];
            int bound = left_bound(sum,target1);

            if(bound == -1){
                break;
            }

            res = Math.min(res,bound - i + 1);
        }

        return res == Integer.MAX_VALUE ? 0 : res;
    }
    //这个函数是起到 寻找相应数字，或者说如果该数不存在就是寻找大于这个数的第一个数
    public int left_bound(int[] num,int target1){
        int l = 0, r = num.length - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(num[mid] == target1){
                r = mid - 1;
            }else if(num[mid] < target1){
                l = mid + 1;
            }else if(num[mid] > target1){
                r = mid - 1;
            }
        }
        if(l == num.length) return -1;
        
        return l;
    }
}

特别注意点：

1.以免漏了相应的情况

此处的sum数组设为nums.length + 1 是因为两个前缀和求差时会忽略了不减任何数时的情况，所以将其设为nums.length + 1，

int[] sum = new int[nums.length + 1];

2.左边界法的使用