在排序数组中查找元素的第一个和最后一个位置_获取数组第一个和最后一个

与二分查找唯一的不同就是注意的地方。 当找到目标元素时，并不是直接返回，而是收紧右侧边界，继续查找，以锁定左侧边界。最后返回左侧边界

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

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

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

#include<iostream>
#include<vector>
using namespace std;
 
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) {
            return { -1,-1 };
        }
        int leftBorder = getLeft(nums, target);
        int rightBorder = getRight(nums, target);
        if (leftBorder == nums.size() || nums[leftBorder] != target){
            return { -1,-1 };
        }
        
        vector<int> p = { leftBorder ,rightBorder };
        return p;
    }
 
private:
    int getLeft(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        
        //寻找左侧边界的二分查找
        while (left <= right) {
            int middle = left + ((right - left) >> 1);  // >>移位运算比 / 操作性能好，另外考虑大数溢出
 
            if (nums[middle] == target) {
                right = middle - 1;  //收紧右侧边界以锁定左侧边界
            }
            else if (nums[middle] < target) {
                left = middle + 1;
            }
            else if (nums[middle] > target) {
                right = middle - 1;
            }
        }
        return left; // 返回左侧边界
 
    }
    
    int getRight(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
 
        //寻找右侧边界的二分查找
        while (left <= right) {
            int middle = left + ((right - left) >> 1);
 
            if (nums[middle] == target) {
                left = middle + 1;
            }
            else if (nums[middle] < target) {
                left = middle + 1;
            }
            else if (nums[middle] > target) {
                right = middle - 1;
            }
        }
        return right; // 返回右侧边界
    }
    
};
 
 
int main() {
    Solution s;
    vector<int> v = { 5,7,7,8,8,10 };
    vector<int> t = s.searchRange(v, 9);
 
    cout << t[0] << " " << t[1] << endl;
 
    system("pause");
    return 0;
}