LeetCode 34：在排序数组中查找元素的第一个和最后一个位置

题目

34. 在排序数组中查找元素的第一个和最后一个位置

题解

Leetcode 手册

官方题解

// 34. 在排序数组中查找元素的第一个和最后一个位置
// find-first-and-last-position-of-element-in-sorted-array

const binarySearch = (nums, target, lower) => {
  let left = 0,
    right = nums.length - 1,
    ans = nums.length;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > target || (lower && nums[mid] >= target)) {
      right = mid - 1;
      ans = mid;
    } else {
      left = mid + 1;
    }
  }
  return ans;
};

var searchRange = function (nums, target) {
  let ans = [-1, -1];
  const leftIdx = binarySearch(nums, target, true);
  const rightIdx = binarySearch(nums, target, false) - 1;
  if (
    leftIdx <= rightIdx &&
    rightIdx < nums.length &&
    nums[leftIdx] === target &&
    nums[rightIdx] === target
  ) {
    ans = [leftIdx, rightIdx];
  }
  return ans;
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange2 = function (nums, target) {
  debugger;
  function search(target) {
    let left = 0,
      right = nums.length;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (nums[mid] >= target) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
  const l = search(target);
  const r = search(target + 1);
  return l == nums.length || l >= r ? [-1, -1] : [l, r - 1];
};

let nums = [5, 7, 7, 8, 8, 10];
let target = 8;
console.log(searchRange(nums, target));
console.log(searchRange2(nums, target));

收获

碰到代码里面有个 >> 操作符，不明白它的作用，查了一下

8.右移运算符（>>） 定义：将一个数的各二进制位全部右移若干位，正数左补 0，负数左补 1，右边丢弃。 例如：a=a>>2 将 a 的二进制位右移 2 位，左补 0 或者 左补 1 得看被移数是正还是负。 操作数每右移一位，相当于该数除以 2。

也就是说

8 >> 1 = 4
8 >> 2 = 2
8 >> 3 = 0