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

问题index.php/tags-41973.html" >���述

给你一个按照非递减顺序排列的整数数组 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]

解题思想

先根据二分查找利用范围找出左边的，再根据二分查找利用范围找出右边的

代码

class Solution {public:    int searchFirst(vector& nums, int target) {        int left = 0, right = nums.size() - 1;        while (left             int mid = left + (right - left) / 2;            if (target == nums[mid]) {                if (mid == 0 || nums[mid] != nums[mid - 1])                    return mid;                else {                    //到左半边寻找                    right = mid - 1;                }            }            else if (target  nums[mid])                left = mid + 1;            else                right = mid - 1;        }        return -1;    }    int searchLast(vector& nums, int target) {        int left = 0, right = nums.size() - 1;        while (left             int mid = left + (right - left) / 2;            if (target == nums[mid]) {                if (mid == nums.size()-1|| nums[mid] != nums[mid + 1])                    return mid;                else {                    //到右半边寻找                    left = mid + 1;                }            }            else if (target  nums[mid])                left = mid + 1;            else                right = mid - 1;        }        return -1;    }    vector searchRange(vector& nums, int target) {        int first = searchFirst(nums, target);        int last = searchLast(nums, target);        return vector{first, last};    }};