检索算法

二分搜索

在计算机科学中，二分搜索（binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

递归方式

function binarySearch( arr, val, start, end ) {
  if ( arguments.length < 4 ) {
    start = 0;
    end = arr.length;
  }

  const copy = arr.slice(start, end);
  const len = copy.length;

  if ( len === 0 ) {
    return -1;
  }

  if ( len === 1 ) {
    return copy[0] === val ? start : -1;
  }

  const idx = Math.floor(len / 2) - 1;
  const mid = start + idx;
  const base = copy[idx];

  if ( val === base ) {
    return mid;
  }

  if ( val < base ) {
    end = mid;
  }
  else {
    start = mid + 1;
  }

  return binarySearch(arr, val, start, end);
}

循环方式

function binarySearch( arr, val ) {
  let start = 0;
  let end = arr.length - 1;

  while ( start <= end ) {
    const mid = Math.floor((start + end) / 2);
    const base = arr[mid];

    if ( base < val ) {
      start = mid + 1;
    }
    else if ( base > val ) {
      end = mid - 1;
    }
    else {
      return mid;
    }
  }

  return -1;
}