先玩一个小游戏。预先给定一个小于100的正整数x，让你猜，猜测过程中给予大小判断的提示，问你怎样快速地猜出来？ 这样猜测最快，先猜50，如果猜对了，结束；如果猜大了，往小的方向猜，再猜25；如果猜小了，往大的方向猜，再猜75；…，每猜测1次就去掉一半的数，就这样可以逐步逼近预先给定的数字。这种思想就是二分法。
在用二分法进行查找时，查找对象的数组必须是有序的，即各数组元素的次序是按其值的大小顺序存储的。其基本思想是先确定待查数据的范围（可用 [left,right] 区间表示），然后逐步缩小范围直到找到或找不到该记录为止。二分法可以用递归或者循环的方式实现。
循环实现方式
function getIndex(arr, num) {
let start = 0,
end = arr.length - 1;
while (start < end) {
let mid = Math.floor((start + end) / 2);
if (arr[mid] === num) {
return mid;
} else if (arr[mid] > num) {
end = mid - 1;
} else {
start = mid + 1;
};
};
};
var arr = [1, 4, 7, 8, 12, 34, 67, 88, 99, 100]
console.log(getIndex(arr, 7));
getIndex函数的作用是在数组arr中查询num，并返回对应的下标。有一数组arr，数组中的元素按值从小到大排列有序。
- 用变量
start、end和mid分别指示待查元素所在区间的下界、上界和中间位置。初始时，start = 0，end = arr.length - 1，mid = Math.floor((start + end) / 2)，其中mid表示当前要二分的数组的中间位置。 - 比较参数
num与arr[mid]值的大小
若arr[mid]==num，则查找成功，结束查找；
若arr[mid]>num，则表明参数num只可能在区间start~mid-1内，修改检索范围。令end=mid-1，start值保持不变；
若arr[mid]<num，则表明参数num只可能在区间mid+1~end内，修改检索范围。令start=mid+1，end值保持不变。 - 循环1、2两步，直到
arr[mid] === num条件成立，返回下标即可。
递归实现方式
function getIndex(arr, amount, start = 0, end = arr.length - 1) {
mid = Math.floor((start + end) / 2);
if (arr[mid] === amount) {
return mid;
} else if (arr[mid] > amount) {
end = mid - 1;
return getIndex(arr, amount, start, end);
} else if (arr[mid] < amount) {
start = mid + 1;
return getIndex(arr, amount, start, end);
} else {
return -1;
};
};
var arr = [1, 4, 7, 8, 12, 34, 67, 88, 99, 100];
console.log(getIndex(arr, 7));
递归实现方式的getIndex函数，参数多了start、end，作用就是在arr中查找下标为start、end之间查询是否有和num相同的元素，返回对应的下标。实现思路和循环实现方式一样，区别就是将修改完毕的start、end作为参数再递归调用，直到 arr[mid] === num 条件成立，返回下标即可。
