LeetCode.034.在排序数据中查找元素的第一个位置和最后一个位置(二周目)

虽然此题先前做过但是再次做起来的时候又是没有啥思路。题目给你一个按照非递减顺序排列的整数数组nums和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target返回[-1, -1]。你必须设计并实现时间复杂度为O(log n)的算法解决此问题。首先想到的肯定也是二分查找但是以往的二分查找都是找到特定的值而这次需要一个区间这就要考虑到首位指针的判定以往的二分查找都是分三种情况mid对应的值大于目标值小于目标值等于目标值如果把其中两项合并比如大于目标值小于等于目标值这样在mid对应的值等于目标值时mid还是会走小于目标值得分支那么就会继续往右边去寻找直到越界这样根据头指针就能找到右边界同理我们能获得左边界。在对左右边界进行判断我们就能获得最终结果。注意leftborder和rightborder都是越界后的首位指针在求结果时要对应的加减1.class Solution { public: vectorint searchRange(vectorint nums, int target) { int leftborder getLeftBorder(nums,target); int rightborder getRightBorder(nums,target); if (leftborder -2 || rightborder -2){ return {-1,-1}; }else if (rightborder - leftborder 1){ return {leftborder 1, rightborder - 1}; }else{ return {-1,-1}; } } private: int getLeftBorder(vectorint nums, int target){ int i 0; int j nums.size() - 1; int mid (i j) / 2; int leftborder -2; while (i j) { if (nums[mid] target) { i mid 1; }else{ j mid - 1; leftborder j; } mid (i j) / 2; } return leftborder; } int getRightBorder(vectorint nums, int target){ int i 0; int j nums.size() - 1; int mid (i j) / 2; int rightborder -2; while (i j) { if (nums[mid] target) { j mid - 1; }else{ i mid 1; rightborder i; } mid (i j) / 2; } return rightborder; } };