【优选算法 二分查找】二分查找算法模板详解：二分查找 ＆ 在排序数组中查找元素的第一个和最后一个位置

     

 

---

 二分查找

---

    题目描述    

---

---

    题目解析    

---

---

    暴力解法    

---

我们可以从左往右遍历一次数组，如果存在 target 则返回数组的下标，否则返回 -1；

时间复杂度 O(N)，因为没有利用数组有序的特点，每次比较只能舍弃一个要比较的数；

---

    二分查找法    

---

所以我们可以把 [1 , 4 ] 这个区间舍弃掉，直接看 [ 5 , 8 ]；仅仅拿 4 和 5 比较一次，就干掉了一大片数；

---

    总结    

---

在一个数组中，随便找一个数，拿这个数和 target 进行比较，并且以拿的这个数分成两个区间，比较后舍弃一部分数，然后再从另一个区间的数中，找下一个要和 target 比较的数；

---

二分查找算法的本质，就是当数组具有“二段性”时，哪怕这个数组是无序的，只要能在这个数组中发现“二段性”，那么也可以使用二分查找；

---

    “二段性”     

---

当我们发现一个规律，然后根据这个规律，选取某一个点，根据这个点，能把数组分成两个区域，根据规律能够有选择地舍弃一部分，进而在另一个部分继续查找的时候，此时，就可以使用二分查找的算法

---

 

我们要从数组中找和 target 进行比较的数，不一定是先从 n/2 的位置开始找，只要找的这个数的点，能把这个区间分成两部分，即满足二段性，进而使用二分查找法；

但是哪怕那么多点可以选择，但是我们都应该先选择 n/2 的位置的点，因为在概率学的数学期望中，我们选择中间的点，时间复杂度是最好的；

---

 

1. nums[mid] < target，left = mid+1
2. nums[mid] = target，return mid
3. nums[mid] > target，right = mid-1

    细节问题    

---

因为当 left = right 的时候，也是要继续判断的，所以 left <= right 为循环判断条件；

时间复杂度，只需要看循环执行多少次：

如何求 x 呢？

---

int mid = (left  + right) / 2，mid 会有溢出风险：

---

如果想不从 n/2 开始查找，可以修改，如下面的写法是从 n/3 开始查找的： 

---

 在排序数组中查找元素的第一个和最后一个位置 

---

---

---

    题目解析     

---

    发现二段性     

---

    方法一：利用数组有序特性，使用简单的二分查找法    

---

如果使用简单的二分查找，创建左指针和右指针，再找中间值，对这个中间值分别进行讨论；如果对于一些特点的情况，如下面的这种情况，这个方法的时间复杂度会非常高；

虽然 mid 指针刚好指向 target，但是不能确定此时的 mid 指向的是在目标连续区域的哪一个位置，从而不好找目标区域的起始位置和终点位置；

所以使用简单二分查找的方法，对于上述情况和类似情况，查找的时间复杂度会近似于暴力查找； 

---

    方法二：在简单二分查找方法的基础上，对二分策略进行优化    

---

回到题目的规律：当发现题目具有二段性，就可以利用二分查找；

---

因为不能同时查找目标区间起始位置和终点位置，所以我们可以先查找起始位置；

利用二段性，我们可以根据目标值起始位置，把数组区间分成两个部分；

---

左边区域的值都是小于 target，右边区域的值都大于等于target，根据 target，在查询目标区域左端点的时候，发现这个数组是有二段性，因此可以使用二分查找：

---

    查找区间左端点     

---

    以 mid 的值来决定 left 和 right 的更新方法    

---

我们设 mid 指向的值为 x，我们要找 >=target 区间的起始位置，拿 x 的值与 target 讨论；

---

• 1. x < target，此时 mid 落在 < target 的区域，不可能有最终结果，所以继续往下执行：

---

---

• 2. x >= target

---

(不同点，之前简单二分查找的方法分三种情况讨论，这里只分两种情况，因为 x= target 并不是最终的结果，因为最终的结果的左端点和右端点)

对于这种情况，对应的做法：

我们虽然[mid , right] 区间的情况一定是都大于 target，但是不知道 [left , mid] 区间的具体情况是都小于 target 还是部分小于 target；所以 right 绝对不能移动到 [left , mid] 这个不确定的区间，因为如果 mid 在修改之前就是目标区间的左端点，让 right = mid -1，[left , right]这个区间就没有 target 了，所以 right = mid 即可；

---

    处理细节问题   

---

    1.循环条件    

---

对于执行循环操作（二分查找操作）的第一个循环条件，是 left <= right，还是 left < right 呢？

一定是选择 left< right ，为什么呢？有两个原因；

---

•      原因一：因为 left = right 的情况不需要放到循环中判断    

我们分三种情况来讨论（ret 为返回的最终结果）：

•     1. 数组中有元素等于 target    

---

前面提到，left 刚开始一直处于 < target 的区间，在 x>= target 的条件下，right=mid，所以right 一定在 ret 右边的区间，threshold 为ret （第一个 target 元素）的前一个元素；

 

因为 left 和 right 的调整方式是 left = mid+1，right = mid，所以 right 一直在>= target 的区域移动，而 left = mid +1，说明 left 是一直想要跳出 < target 的区域的；

所以当 left 和 right 调整到最后，循环结束，此时 left 一定会和 right 相等，此时我们在循环结束后单独判断相遇点和 target 是否相等即可；如果 left = right ，那么两个指针指向的位置，一定就是目标区间左端点 ret，所以循环条件只需要判断 left < right 即可；

---

•     2. 数组中所有元素全都大于 target    

---

如果所有数组元素都大于 target，那么整个过程只有 right 指针在不断向左边移动，直到 left 和 right 相遇；

哪怕相遇，也没有最终结果，所以这种情况下，我们只需要在left < right 时执行循环，循环退出，left=right；

此时我们只需要拿当前两个指针指向的值和 target 比较：相同则回到第一种情况，这个值就是目标区间的左端点；不相同则返回 [-1,-1]；

---

•    3. 数组中所有元素全都小于 target    

---

这种情况和第二种情况同理：

整个更新过程都只有 left 在移动，循环退出时，left = right，只需要判断当前指针的值和 target 是否相等即可，相等则这个值就是目标区域的起始位置 ret，否则返回 [-1,-1]；

---

•    原因二：如果在循环条件中判断 left = right，会出现死循环   

---

 什么时候会出现死循环，就是整个数组中有元素等于 target 的时候：

如果循环条件是 while(left <= right){ ..... }，此时left = right ，更新的 mid还是指向 left，right 所在位置，此时满足 x <= target 条件，right=mid，所以 right = left，left 和 right 就会一直停在一个地方循环更新结果，这种情况下就会出现死循环；

---

    2. 求中点操作    

---

求中点操作，也就是在定义 left 和 right 之后，求 mid 的操作； 

• 1. mid = left + ( right - left ) / 2 ;

• 2. mid = left +( right - left +1 ) /2 ;

这两种求中点的操作，区别在于数组元素是偶数时，更新 mid 的位置不同；这两种方法在简单二分情况，如第一题的情况都是可以用的，但是这种情况下不能用 mid = left + (right - left +1)/2 求中点；

---

如果是用第二种方法 mid = left + (right - left +1)/2，此时 mid 的位置：

---

• 如果上图条件中，target > 3，那么此时 mid < target ，left = mid+1，程序结束，此时是没问题的；

---

• 但是，如果 target <=3，那么此时 mid>=target，此时调整 right = mid，就又进入死循环了：

---

所以，在求左端点时，只能用 mid = left +(right - left )/2 来求中点；

---

    查找区间右端点    

---

根据查找右端点，依旧可以把整个区间分成两部分，<=target，>target :

---

   根据 mid 与 target 的关系决定更新操作    

---

    1. x <= target    

---

因为我们要保证在调整 left 和 right 的过程中，右端点一定要在 [left，right] 区间，所以当前这种情况，我们应该移动 left：

---

    2. x > target    

---

因为 x > target，所以mid 所在位置一定是在目标区域之外，因此更新 right = mid -1；

    处理细节问题    

---

    1. 循环条件   

---

 

---

    2. 求中点的操作    

---

循环条件和求左端点相同，不同的是求中点的公式 

---

•  1. mid = left + ( right - left ) / 2 ;

---

• 2. mid = left +( right - left +1 ) /2 ;

---

这两种求中点的操作，区别在于数组元素是偶数时，更新 mid 的位置不同；这两种方法在简单二分情况，如第一题的情况都是可以用的，但是这种情况下不能用 mid = left + (right - left )/2 求中点；

为了接下来的操作不和求左端点的时候弄混，要牢记此时要求的是右端点，接下来的假设都是为了能求出右端点：

---

如果是用第二种方法 mid = left + (right - left )/2，此时 mid 的位置：

---

• 如果上图条件中，target < 2，那么此时 mid > target ，right = mid-1，程序结束，此时是没问题的；

---

• 但是，如果 target >=3，那么此时 mid>=target，此时调整 left = mid，就又进入死循环了：

 

---

所以，在求右端点时，只能用 mid = left +(right - left +1 )/2 来求中点，在求右端点时，为什么用这条公式求中点不会出现死循环呢？

---

用 mid = left +(right - left +1 )/2  来求中点，此时 mid 在 right 的位置，如果此时 x > target，right=mid-1，此时不满足 left<right 的条件，会结束循环；如果 x<= target，left = mid :

此时也不满足 left<right 的条件，也会结束循环，所以在求右端点的时候，用 mid = left +(right - left +1)/2  来求中点，就不会出现死循环；

    编写代码    

---

---

    总结二分模板   

---