检索算法

二分搜索

在计算机科学中，二分搜索（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;}