如何用二分查找在一个数组中搜索某个值，判断它是否在该数组中。

[pwstrick]

如何用二分查找在一个数组中搜索某个值，判断它是否在该数组中。

[hexh250786313]

// 二分查找
// 前提：二分查找要求数组有序，无序不能用此算法
// 这是数组升序的情况，降序的话把下面的 reverse 改为 true 即可
function binarySearch(
  arr: number[],
  compare: typeof findFirst,
  target: number
) {
  let highIdx = arr.length - 1;
  let lowIdx = 0;

  while (lowIdx <= highIdx) {
    const midIdx = (highIdx + lowIdx) >> 1;
    const cmp = compare({ arr, target, midIdx });

    if (cmp < 0) {
      highIdx = midIdx - 1;
    } else if (cmp > 0) {
      lowIdx = midIdx + 1;
    } else {
      return midIdx;
    }
  }

  return -1;
}

function findFirst({
  arr,
  target,
  reverse,
  midIdx,
}: {
  arr: number[];
  target: number;
  midIdx: number;
  reverse?: boolean;
}) {
  let cmp = target - arr[midIdx];
  if (reverse) cmp = -cmp;
  if (cmp === 0) return arr[midIdx - 1] !== target ? 0 : -1;
  return cmp;
}

function findLast({
  arr,
  target,
  reverse,
  midIdx,
}: {
  arr: number[];
  target: number;
  midIdx: number;
  reverse?: boolean;
}) {
  let cmp = target - arr[midIdx];
  if (reverse) cmp = -cmp;
  if (cmp === 0) return arr[midIdx + 1] !== target ? 0 : 1;
  return cmp;
}

const test: any[] = [-1, 0, 4, 5, 5, 5, 5, 6, 9, 10, 11, 12];
// const test: any[] = [-1, 0, 4, 5, 5, 6, 9, 10, 11, 12];
// const test: any[] = [-1, 0, 4, 5, 6, 9, 10, 11, 12];
// const test: any[] = [5, 5, 6, 9, 10, 11, 12];
// const test: any[] = [5, 6, 9, 10, 11, 12];
// const test: any[] = [-1, 0, 4, 5, 5];
// const test: any[] = [-1, 0, 4, 5];
// const test: any[] = [-1, 0, 4, 6, 9, 10, 11, 12];
console.log(binarySearch(test, findFirst, 5));                           // 找到第一个 5
console.log(binarySearch(test, findLast, 5));                            // 找到最后一个 5
console.log(binarySearch(test, (...rest) => findFirst(...rest) - 1, 5)); // 找到比 5 小的最大的数
console.log(binarySearch(test, (...rest) => findLast(...rest) + 1, 5));  // 找到比 5 大的最小的数

console.log(test);