题目

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

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

思路

寻找target在数组里的左右边界，有如下三种情况：

  • target 在 nums[0] ~ nums[n-1] 中，nums 中存在 target。例如 nums = [5,7,7,8,8,10]，target = 8，返回 [3，4]。
  • target 在 nums[0] ~ nums[n-1] 中，nums 中不存在 target。例如 nums = [5,7,7,8,8,10]，target = 6，返回 [-1,-1]。
  • target < nums[0] 或者 target > nums[n-1]。例如 nums = [5,7,7,8,8,10], target = 4，返回 [-1,-1]。

专注于寻找右区间，然后专注于寻找左区间，左右根据左右区间做最后判断。不要上来就想如果一起寻找左右区间，搞着搞着就会顾此失彼，绕进去拔不出来了.

  1. //二分查找左右边界
  2. /*
  3. 1.target比数组里所有元素都小;
  4. 2.target比数组里所有元素都大；
  5. 3.target在数组元素之间，但是没有值和target相等的元素；
  6. 4.能够找到和target相等的元素，且唯一；
  7. 5.能够找到和target相等的元素，但不唯一；
  8. */
  9. class Solution {
  10. public:
  11.     vector<int> searchRange(vector<int>& nums, int target) {
  12.         int leftborder = LeftBorder(nums, target);
  13.         int rightborder = RightBorder(nums, target);
  14.         //情况1和情况2和情况3
  15.         if(leftborder==-2 || rightborder==-2) return {-1,-1};
  16.         //情况4和5
  17.         else return {leftborder,rightborder};
  18.     }
  19. private:
  20.     //寻找左边界（包括target元素本身）
  21.     int LeftBorder(vector<int>& nums, int target){
  22.         int left = 0; //上限
  23.         int right = nums.size()-1; //下限
  24.         int leftborder = -2; //初始化左边界值为-2
  25.         while(left<=right){
  26.             int mid = left+((right-left)/2); //中间
  27.             //等于的时候也缩小下限，往目标元素值左边逼近
  28.             if(nums[mid]==target){
  29.                 leftborder = mid; //不断更新边界值
  30.                 right = mid-1; //接着缩小范围，看看它左边还有没有等于target的元素
  31.             }
  32.             else if(nums[mid]>target){
  33.                 right = mid-1;
  34.             }
  35.             else left = mid+1;
  36.         }
  37.         //最后返回左边界的索引
  38.         return leftborder;
  39.     }
  40.     //寻找右边界（包括target元素本身）
  41.     int RightBorder(vector<int>& nums, int target){
  42.         int left = 0; //上限
  43.         int right = nums.size()-1; //下限
  44.         int rightborder = -2; //初始化右边界值为-2
  45.         while(left<=right){
  46.             int mid = left+((right-left)/2); //中间
  47.             //等于的时候也缩小下限，往右边逼近
  48.             if(nums[mid]==target){
  49.                 rightborder = mid; //不断更新边界值
  50.                 left = mid+1; //接着缩小范围，看看它右边还有没有等于target的元素
  51.             }
  52.             else if(nums[mid]<=target){
  53.                 left = mid+1;
  54.             }
  55.             else right = mid-1;
  56.         }
  57.         //最后返回右边界的索引
  58.         return rightborder;
  59.     }
  60. };

普通二分查找是，当 nums[mid] == target 时，直接返回 mid，而在本题中，则是要继续向左或向右查找，看是否还有和target相等的数组元素。