二分查找

[ChenPt]

二分查找法适用于已经排好序的数据结构

// 递归版本
function binary_search(arr, start, end, value) {
  if(start > end) {
    return -1
 }
  let mid = Math.floor((start + end) / 2)
  if(value > arr[mid]) {
    return binary_search(arr, mid+1, end, value)
  }
  if(value < arr[mid]) {
    return binary_search(arr, start, mid - 1, value)
  }
  return mid
}

// 利用函数柯里化，只需要传`arr`和`value`两个参数
function curry_binary_search(arr, value) {
  return binary_search.call(null, arr, 0, arr.length - 1, value)
}
// test
curry_binary_search([1,2,3,4,5,6,7,8,9,10,11], 1)  // 0 ， 返回`1`在数组中的序号