js的二分法

二分法，即在一个有序的数组里查找一个已知其值的元素位置
实现方法有两种：

//循环二分法
function cycle_dichotomy(arr,value) {
  let lowIndex = 0,highIndex = arr.length - 1,midIndex;
  while(lowIndex <= highIndex) {
    midIndex = Math.floor((highIndex + lowIndex) / 2);
    if(arr[midIndex] == value) {
      return midIndex;
    }else if(arr[midIndex] > value) {
      highIndex = midIndex - 1;
    }else {
      lowIndex = midIndex + 1;
    }
  }
  return -1;
}


//递归二分法
function recursive_dichotomy(arr,value,lowIndex,highIndex) {
  if(lowIndex <= highIndex) {
    let midIndex = Math.floor((lowIndex + highIndex) / 2);
    if(arr[midIndex] == value) {
      return midIndex;
    }else if(arr[midIndex] > value) {
      return recursive_dichotomy(arr,value,lowIndex,midIndex - 1);
    }else {
      return recursive_dichotomy(arr,value,midIndex + 1,highIndex);
    }
  }
  return -1;
}

//eg:
let eg_arr = [1,2,3,4,5,6,7,8,9];
let eg_value = 3;
console.log(cycle_dichotomy(eg_arr,eg_value));  // 2
console.log(recursive_dichotomy(eg_arr,eg_value,0,8));  // 2

循环二分法效率更高，递归容易造成堆栈溢出