Leetcode 86 【二分查找】在排序数组中查找元素的第一个和最后一个位置-平芜编程栈

二分搜索算法核心代码模板 | labuladong 的算法笔记

1 温故而知新

题目

704. 二分查找

给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果target存在返回下标，否则返回-1。

你必须编写一个具有O(log n)时间复杂度的算法。
示例 1:

输入:nums= [-1,0,3,5,9,12],target= 9输出:4解释:9 出现在nums中并且下标为 4

示例 2:

输入:nums= [-1,0,3,5,9,12],target= 2输出:-1解释:2 不存在nums中因此返回 -1

提示：

你可以假设nums中的所有元素是不重复的。
n将在[1, 10000]之间。
nums的每个元素都将在[-9999, 9999]之间。

代码实现

重新写的时候犯了个小错误，贴上解答错误的代码

class Solution { public: int search(vector<int>& nums, int target) { int left = 0 ; int right = nums.size() -1 ; while (left < right){ int mid = (right - left) / 2 + left ; if (nums[mid] == target){ return mid; }else if (nums[mid] > target){ right = mid - 1 ; }else{ left = mid + 1 ; } } return -1; } };

错误：循环条件，left <= right ，两个可以相等，对于数组内只有单个元素的考虑（否则会错误的跳出循环返回 -1）

class Solution { public: int search(vector<int>& nums, int target) { int left = 0 ; int right = nums.size() - 1; while(left <= right){ int mid = left + (right - left ) / 2 ; if(nums[mid] == target ){ return mid ; }else if (nums[mid] < target ){ left = mid + 1 ; }else if (nums[mid] > target ){ right = mid - 1; } } return -1; } };

框架伪码

int binarySearch(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while (...) { int mid = left + (right - left) / 2; if (nums[mid] == target) { ... } else if (nums[mid] < target) { left = ... } else if (nums[mid] > target) { right = ... } } }

题目

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]

示例 3：

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

代码实现

这个题目怎么觉得有点像滑动窗口，直接看看以前提交的代码回顾一下。

using namespace std ; class Solution { public: int left_bound(vector<int>& nums ,int target){ int left = 0 , right = nums.size() - 1 ; while (left <= right ){ int mid = left + (right - left ) / 2 ; if (nums[mid] < target ){ left = mid + 1 ; }else if (nums[mid] > target){ right = mid - 1 ; }else if (nums[mid] == target){ right = mid - 1 ; } } if (left < 0 || left >= nums.size() || nums[left] != target){ return -1 ; } return left ; } int right_bound(vector<int>& nums ,int target){ int left = 0 , right = nums.size() - 1 ; while (left <= right ){ int mid = left + (right - left ) / 2 ; if (nums[mid] < target ){ left = mid + 1 ; }else if (nums[mid] > target){ right = mid - 1 ; }else if (nums[mid] == target){ left = mid + 1 ; } } if (right < 0 || right >= nums.size() || nums[right] != target){ return -1 ; } return right ; } vector<int> searchRange(vector<int>& nums, int target) { int left = left_bound(nums,target); int right = right_bound(nums,target); return{ left , right }; } };

我知道了，一看这个题解，我知道我当时根本不会这个题目，我先记下来的。

class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { // 直接调用原名称的左右边界查找函数 int left = left_bound(nums, target); int right = right_bound(nums, target); return {left, right}; } private: // 查找左边界 int left_bound(vector<int>& nums, int target) { int left = 0, right = nums.size()-1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { right = mid - 1; // 锁定左侧边界 } } // 越界或值不匹配则返回-1 if (left < 0 || left >= nums.size() || nums[left] != target) { return -1; } return left; } // 查找右边界 int right_bound(vector<int>& nums, int target) { int left = 0, right = nums.size()-1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { left = mid + 1; // 锁定右侧边界 } } // 越界或值不匹配则返回-1 if (right < 0 || right >= nums.size() || nums[right] != target) { return -1; } return right; } };

其实很清晰了，就是在做一个左边界查找和右边界查找索引的工作，根本没那么难。

自己动手写的错的代码

class Solution { private: int left_bound (vector<int>& nums, int target){ int left = 0 ; int right = nums.size() -1 ; while(right >= left){ int mid = left + (right - left) / 2 ; if(nums[mid] == target){ right = mid - 1; }else if (nums[mid] > target){ right = mid - 1; }else{ left = mid +1 ; } } if (left < 0 || left >= nums.size() || nums[left] != target) { return -1; } return left; } int right_bound (vector<int>& nums, int target){ int left = 0 ; int right = nums.size() -1; while(right >= left){ int mid = left + (right - left) / 2 ; if(nums[mid] == target){ left = mid +1 ; }else if (nums[mid] > target){ right = mid - 1; }else{ left = mid +1 ; } } if (left < 0 || left >= nums.size() || nums[left] != target) { return -1; } return right; } public: vector<int> searchRange(vector<int>& nums, int target) { int left = left_bound(nums,target); int right = right_bound(nums,target); return{ left, right }; } };

错误注释

class Solution { private: int left_bound (vector<int>& nums, int target){ int left = 0 ; int right = nums.size() -1 ; while(right >= left){ int mid = left + (right - left) / 2 ; if(nums[mid] == target){ right = mid - 1; }else if (nums[mid] > target){ right = mid - 1; }else{ left = mid +1 ; } } // 错误1（非致命）：left初始为0且只增不减，不可能<0，这个判断多余 if (left < 0 || left >= nums.size() || nums[left] != target) { return -1; } return left; // left_bound的返回值是正确的，这里没问题 } int right_bound (vector<int>& nums, int target){ int left = 0 ; int right = nums.size() -1; while(right >= left){ int mid = left + (right - left) / 2 ; if(nums[mid] == target){ left = mid +1 ; }else if (nums[mid] > target){ right = mid - 1; }else{ left = mid +1 ; } } // 错误2（致命）：校验的是left，但right_bound的结果存在right里，left此时可能越界 // 比如nums=[1,2,2,3], target=2，循环结束后left=3，nums[3]=3≠2，直接错误返回-1 // 正确应该校验right的合法性和值 if (left < 0 || left >= nums.size() || nums[left] != target) { return -1; } // 这里return right是正确的，但上面的校验逻辑错了，导致根本走不到这一步 return right; } public: vector<int> searchRange(vector<int>& nums, int target) { int left = left_bound(nums,target); int right = right_bound(nums,target); return{ left, right }; } };

修正后

class Solution { private: int left_bound (vector<int>& nums, int target){ int left = 0 ; int right = nums.size() -1 ; while(right >= left){ int mid = left + (right - left) / 2 ; if(nums[mid] == target){ right = mid - 1; }else if (nums[mid] > target){ right = mid - 1; }else{ left = mid +1 ; } } if (left >= nums.size() || nums[left] != target) { return -1; } return left; } int right_bound (vector<int>& nums, int target){ int left = 0 ; int right = nums.size() -1; while(right >= left){ int mid = left + (right - left) / 2 ; if(nums[mid] == target){ left = mid +1 ; }else if (nums[mid] > target){ right = mid - 1; }else{ left = mid +1 ; } } if (right>= nums.size() || nums[right] != target) { return -1; } return right; } public: vector<int> searchRange(vector<int>& nums, int target) { int left = left_bound(nums,target); int right = right_bound(nums,target); return{ left, right }; } };

承认偷懒了，校验逻辑这里直接复制粘贴了，没有自己再好好核对一遍。

2 二分查找归类

第一个，最基本的二分查找算法：

因为我们初始化 right = nums.length - 1 所以决定了我们的「搜索区间」是 [left, right] 所以决定了 while (left <= right) 同时也决定了 left = mid+1 和 right = mid-1 因为我们只需找到一个 target 的索引即可 所以当 nums[mid] == target 时可以立即返回

第二个，寻找左侧边界的二分查找：

因为我们初始化 right = nums.length 所以决定了我们的「搜索区间」是 [left, right) 所以决定了 while (left < right) 同时也决定了 left = mid + 1 和 right = mid 因为我们需找到 target 的最左侧索引 所以当 nums[mid] == target 时不要立即返回 而要收紧右侧边界以锁定左侧边界

第三个，寻找右侧边界的二分查找：

因为我们初始化 right = nums.length 所以决定了我们的「搜索区间」是 [left, right) 所以决定了 while (left < right) 同时也决定了 left = mid + 1 和 right = mid 因为我们需找到 target 的最右侧索引 所以当 nums[mid] == target 时不要立即返回 而要收紧左侧边界以锁定右侧边界 又因为收紧左侧边界时必须 left = mid + 1 所以最后无论返回 left 还是 right，必须减一

三类代码合起来看

int binary_search(vector<int>& nums, int target) { int left = 0, right = nums.size()-1; while(left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if(nums[mid] == target) { // 直接返回 return mid; } } // 直接返回 return -1; } int left_bound(vector<int>& nums, int target) { int left = 0, right = nums.size()-1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别返回，锁定左侧边界 right = mid - 1; } } // 判断 target 是否存在于 nums 中 if (left < 0 || left >= nums.size()) { return -1; } // 判断一下 nums[left] 是不是 target return nums[left] == target ? left : -1; } int right_bound(vector<int>& nums, int target) { int left = 0, right = nums.size()-1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别返回，锁定右侧边界 left = mid + 1; } } // 由于 while 的结束条件是 right == left - 1，且现在在求右边界 // 所以用 right 替代 left - 1 更好记 if (right < 0 || right >= nums.size()) { return -1; } return nums[right] == target ? right : -1; }