二分法

二分法是算法中比较重要的一个算法，昨天刷题遇到了，今天来总结一下 二分法就是逐渐缩小一半区间，直到匹配成功 二分法适合已经排序好的数组

循环二分法

// n 是数组长度， v是猜测的数， a是数组 function xunhuan(n, v, a) { // 当左右区间相等时候就表示找到了那个数的位置 let left = 0 let right = n while (left < right) { let mid = Math.floor((left + right) / 2); if (a[mid] >= v) { if (mid === 0 || a[mid - 1] < v) return mid right = mid } else { left = mid ; } } }

递归二分法

// a是数组 v是猜测的数，left是左边界，right是右边界 function digui(a,v,left,right) { int mid = (left + right) / 2; if (a[mid] == v) { return mid; } else if (a[mid] > v) { //如果中间值大于要找的值则从左边一半继续递归 return digui(a, v, left, mid - 1); } else { //如果中间值小于要找的值则从右边一半继续递归 return digui(a, v, mid + 1, a.length-1); } }