/*
 * @lc app=leetcode.cn id=34 lang=javascript
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  // 1. 双指针法
  // const len = nums.length;
  // let left = 0;
  // let right = len - 1;
  // let leftIdx = -1;
  // let rightIdx = -1;

  // while (left <= right && (leftIdx === -1 || rightIdx === -1)) {
  //   const leftVal = nums[left];
  //   const rightVal = nums[right];
  //   if (leftVal === target && leftIdx === -1) {
  //     leftIdx = left
  //   }
  //   if (rightVal === target && rightIdx === -1) {
  //     rightIdx = right
  //   }
  //   if (leftVal < target) {
  //     left++
  //   } else if (rightVal > target) {
  //     right--
  //   }
  // }

  // return [leftIdx, rightIdx]


  // 2. 二分法分别查找最左边和最右边
  function binarySearch(arr, target, lower) {
    const len = arr.length;
    let left = 0;
    let right = len - 1;
    let mid;
    while (left <= right) {
      mid = (left + right) >> 1;
      let cur = arr[mid]

      if (cur === target) {
        if (lower) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else if (cur > target) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    }
    return lower ? left : right
  }

  const left = binarySearch(nums, target, true)
  const right = binarySearch(nums, target, false)
  if (left > right) return [-1, -1]
  return [left, right]
};
// @lc code=end

console.log(searchRange([5, 7, 7, 8, 8, 10], 8))
console.log(searchRange([5, 7, 7, 8, 8, 10], 6))
console.log(searchRange([1, 3], 1))