#include "s0034_find_first_and_last_position_of_element_in_sorted_array.hpp"

// 闭区间写法
vector<int> S0034::searchRange1(vector<int>& nums, int target) {
  int len = nums.size();
  int l{0};
  int r = len - 1;
  while (l <= r) {
    int m = (l + r) >> 1;
    if (target < nums[m]) {
      r = m - 1;
    } else if (nums[m] < target) {
      l = m + 1;
    } else {
      l = r = m;
      while (l >= 0) {
        if (nums[l] == target) {
          --l;
        } else {
          break;
        }
      }
      while (r <= len - 1) {
        if (nums[r] == target) {
          ++r;
        } else {
          break;
        }
      }
      return vector<int>{l + 1, r - 1};
    }
  }
  return vector<int>{-1, -1};
}

// 开区间写法
vector<int> S0034::searchRange2(vector<int>& nums, int target) {
  int len = nums.size();
  int l{0};
  int r = len;
  while (l < r) {
    int m = (l + r) >> 1;
    if (target < nums[m]) {
      r = m;
    } else if (nums[m] < target) {
      l = m + 1;
    } else {
      l = r = m;
      while (l >= 0) {
        if (nums[l] == target) {
          --l;
        } else {
          break;
        }
      }
      while (r <= len - 1) {
        if (nums[r] == target) {
          ++r;
        } else {
          break;
        }
      }
      return vector<int>{l + 1, r - 1};
    }
  }
  return vector<int>{-1, -1};
}