34. Find First and Last Position of Element in Sorted Array

這題一口氣訓練的兩件事

一個就是基本的binary search

另一個就是, 怎麼找極值

詳細網路上很多, 這邊就不特別紀錄了

class Solution {
public:
  vector<int> searchRange(vector<int> &nums, int target) {
    int l = 0;
    int r = nums.size() - 1;
    bool hasTarget = false;
    while(l <= r){
      int mid = (l + r) /2;
      if(nums[mid] == target){
        hasTarget = true;
        break;
      }else if (nums[mid] <target){
        l = mid + 1;
      }else if(nums[mid] > target){
        r = mid - 1;
      }
    }
    if(!hasTarget) return {-1, -1};
    vector<int> res;
    // find left
    l = 0;
    r = nums.size() - 1;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (nums[mid] == target) {
        r = mid - 1;
      } else if (nums[mid] < target) {
        l = mid + 1;
      } else if (nums[mid] > target) {
        r = mid - 1;
      }
    }
    res.push_back(l);
    // find right
    l = 0; r = nums.size()- 1;
    while(l <= r){
      int mid = (l + r) /2;
      if(nums[mid] == target){
        l = mid + 1;
      }else if (nums[mid] < target){
        l = mid + 1;
      }else if (nums[mid] > target){
        r = mid - 1;
      }
    }
    res.push_back(r);
    return res;
  }
};