二分查找总结——二分查找细节分析 + 红蓝染色法

1. 写在前面

　　本文为个人学习总结，二分算法参考：B站Up：灵茶山艾府（二分查找 红蓝染色法）

视频链接：https://www.bilibili.com/video/BV1AP41137w7/

Leetcode题目：34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

测试样例1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

测试样例2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

2. 二分查找的区间细节分析

　　二分查找(Binary Search)的算法思想是十分简单的，但二分法的细节却惊人的多。以下是一份二分查找的代码示例，在敲定二分法的代码时，我们通常会遇到注释的细节问题：

  // 下方代码的作用：查找有序正整数数组nums[]中第一个≥target的数的位置（下标）

  // 待查找数组 nums[], 待查找数 target
  int left = 0; // 数组最左端元素下标
  int right = nums.length - 1; // 数组最右端元素下标

  while(left <= right){ // 是left<right呢还是left<=right呢
    int mid = (left + right) / 2;
    if(nums[mid] >= target){ // 可以是nums[mid] > target吗
        right = mid - 1; // 是right = mid - 1呢还是right = mid呢？
    }else{
        left = mid + 1;  // 同理，可以是left = mid 吗？
     }
  }
  return left;

　　其实，上面的情况都是可能存在的，而具体的代码写法要取决于我们对于查找区间的开闭选定，这个区间其实指的就是我们查找的范围，即left 和 right圈定的范围，常见的区间选定方法有：

1. 左闭右闭 [left, right]
2. 左闭右开 [left, right)
3. 左开右开 (left, right)

　　当我们在写二分查找的代码的时候，一定要先明确我们选定的区间的闭合情况，在整个二分查找的过程中都应该去遵循这个区间，才能保证我们的二分查找代码不出错。

　　什么意思呢？我们来对不同情况分析一下。

① 左闭右闭[left, right]

　　区间左闭右闭，也就是说我们每次二分查找的时候是包含left和right索引指向的那个数的，那么，我们对left和right的初始化应该如下所示：

  // 待查找数组 nums[], 待查找数 target
  // 假设nums为[1，2，5，8，11，12，13]

  int left = 0; // 数组最左端元素下标
  int right = nums.length - 1; // 数组最右端元素下标

  while(left <= right){ 
    int mid = (left + right) / 2;
    if(nums[mid] >= target){ 
        right = mid - 1;
    }else{
        left = mid + 1;
     }
  }
  return left;

　　在代码中，left指向nums的第一个数，right指向nums的最后一个数，此时查找范围涵盖了整个数组，没有问题，对于其他的编写细节：
i) while(left<=right)
　　前文提及，我们在编写代码的过程中需要一直遵守我们选择的区间，那么，我们就需要去判断left=right对于当前选择的区间是不是合法的。
　　当left=right时，显然，对于[left, right]这个区间有意义，因此我们此时还不能结束循环。循环条件为left<=right

ii) right = mid - 1 || left = mid + 1
　　由于我们的区间是左闭右闭区间，包含两端，如果right = mid，我们的下一次查找区间为：[left, mid]，此时mid指向的元素又被包括进来了，但是在之前的if条件判断中，我们知晓了nums[mid]与target的关系，所以下一次查找没有必要将mid指向的元素包括进来了，因此right = mid - 1。
　　left = mid + 1的情况同理。

  // nums为[1，2，5，8，11，12，13]， target为2

  第一次查找索引区间：[0, 6], mid = 3
  nums[mid] = 8 > 2， right = mid - 1 = 2
  
  下一次查找索引区间：[0, 2] (1,2,5)

  //假设right = mid 则下一次查找区间：[0, 3]，包括的元素为1，2，5，8
  //但我们之前已经知道了mid指向的8是不符合条件的了，所以没有必要包含到下一次查找了

① 左闭右开[left, right）

　　左闭右开，即不包含right指向的数，那么我们的代码会发生如下变化：

  // 待查找数组 nums[], 待查找数 target
  // 假设nums为[1，2，5，8，11，12，13]

  int left = 0; 
  int right = nums.length; // 数组长度！这里变了！

  while(left < right){  // 循环条件变了！
    int mid = (left + right) / 2;
    if(nums[mid] >= target){ 
        right = mid;  // 变啦！
    }else{
        left = mid + 1;
     }
  }
  return left;

i) 变化一：right的值
　　int right = nums.length;
　　区间为左闭右开，即不包含right指向的元素。因此，为了将查找范围涵盖整个数组，right不能为nums.length - 1，否则会丢失数组最后一个元素。
ii) 变化二：循环条件
　　在左闭右开区间 [left, right) 中，left = right是没有意义的，因此在left = right时应该结束循环。故循环条件为left<right，而非left<=right。
** iii) 变化三：下一次查找的right值**
　　right = mid， 即下一次查找的区间为：[left, mid)，下一次查找不会包含mid了，是符合我们之前的做法的。left = mid + 1是因为区间左闭，假如left = mid，下一次查找又会将mid指向的元素包括进来了，没有必要。

3. 红蓝染色法

未完待续。