二分查找

很经典的查找问题， 就是在一个有序列表中查找目标值， 一般我们认为列表是升序的接口

function binarySearch(arr, l, r, target) {
  if (l > r) {
    return -1;
  }
  let mid = Math.floor(l + (r - l) / 2);
  if (arr[mid] === target) {
    return mid;
  } else {
    if (arr[mid] > target) {
      return binarySearch(arr, l, mid - 1, target);
    } else {
      return binarySearch(arr, mid + 1, r, target);
    }
  }
}

扩展问题， 比如获取某一个在列表的中的范围， 比如

[1, 2 ,3 ,4, 4, 4, 5, 6]找到4的范围为[3, 5]

function searchRange(arr, l, r, target) {
  const mid = binarySearch(arr, l, r, target);
  if (mid === -1) return [-1, -1];
  let start = mid,
    end = mid;
  while (start - 1 >= l && arr[start - 1] === target) {
    start--;
  }
  while (end + 1 <= r && arr[end + 1] === target) {
    end++;
  }

  return [start, end];
}