题号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]

• 我的题解

  class Solution {
  public:
      vector<int> searchRange(vector<int>& nums, int target) {
          int n = nums.size();
          int left = 0;
          int right = n - 1;
          int middle = 0;
          int curl, curr = 0; 
          int flag = 0;
          while (left <= right){
              middle = left + ((right - left) >> 1);
              curl = middle;
              curr = middle;
              if(nums[middle] < target){
                  left = middle + 1;
              }
              else if (nums[middle] > target){
                  right = middle - 1;
              }
              else{
                  for(int i = left; i<= right; i++){
                      if(nums[i] == target){
                          if(curl == middle && flag == 0){
                              curl = i;
                              flag = 1;
                          }
                          else{
                              curr = i;
                          }
                      }
                  }
                  return {curl, curr};          
              }
          }
          return {-1, -1};        
      }
  };
  

• 总结

  • 输出格式：
    • 要求[a, b]，函数返回{a, b}即可
  • 主题思路遵循代码随想录二分法模板（左闭右闭）
  • 这里新增flag标志位，
    • 若输出区间左边界 curl 等于寻找到的 middle 值且 flag 为 0（即未被修改），则将此时找到的值为 target 的最小序号 i 赋值给 curl ，并将标志位置为 1
    • 此后若继续寻找到了符合要求的边界值，将其赋给右边界 curl
  • 需记忆的点：vector<int> searchRange(vector<int>& nums, int target){ … }