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

tags: leetcode

問題

何故かExploreだと名前が"Search for a Range"になっていますが, 同じ問題です

• Explore
• Problems

アイデア

昇順に整列された配列のうち, targetと一致するものの始点と終点を求めろというもの. 対数時間で求めよという指定から二分探索を使うと考えられます.

targetと一致する要素の数列の左端と右端を二分探索で求めれば対数時間で計算することが可能です

解法

新たに関数を用意します. これをbinsearchとして引数に右端から探索するか, 左端から探索するかを決めるフラグを入れます.

1. このフラグがtrueのとき, 中央の値がtargetと同じときは左側に探索範囲をずらす(右端を中央にする)
2. falseのときは探索範囲を右側にずらす
3. 中央の値がtargetよりも大きい時は探索範囲を左側にずらす
4. 中央の値がtargetよりも小さい時は探索範囲を右側にずらす

この処理はまとめることが可能なのでコード上ではまとめて表現します

計算量

配列の長さを$N$とします. 探索する範囲を半々にしているので

• 時間計算量
  • $O(\log N)$
• 空間計算量
  • $O(N)$

C++

class Solution {
public:
  vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> result = {-1, -1};
    
    int leftIdx = binsearch(nums, target, true);
    
    if (leftIdx == nums.size() || nums[leftIdx] != target) {
      return result;
    }
    
    result[0] = leftIdx;
    result[1] = binsearch(nums, target, false) - 1;
    
    return result;
  }
  
private:
  int binsearch(vector<int>& nums, int target, bool isLeft) {
    int left = 0, right = nums.size();
    
    while (left < right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] > target || (isLeft && target == nums[mid]))
        right = mid;
      else
        left = mid + 1;
    }
    return left;
  }
};