二分查找利用已经排好序的数组，每次查找可以将查找范围减半，查找范围内只剩一个数据时查找结束。
代码模板 #
简单题的模板几乎都是统一的，根据题目的条件再灵活调整就可以了，比如 704. 二分查找。
var search = function(nums, target) {
let low = 0, high = nums.length - 1;
while (low <= high) {
const mid = Math.floor((high - low) / 2) + low;
const num = nums[mid];
if (num === target) {
return mid;
} else if (num > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
};
其它几乎同样模版的题目：
如果要查找两数之和而不是直接的 target，稍微复杂一点比如 167. 两数之和 II - 输入有序数组
var twoSum = function(numbers, target) {
for (let i = 0; i < numbers.length; i++) {
let low = i + 1
let high = numbers.length - 1
while (low <= high) {
let mid = Math.floor((high - low) / 2) + low
if (numbers[mid] + numbers[i] == target) {
return [i+1, mid+1]
} else if (numbers[mid]+numbers[i] > target) {
high = mid - 1
} else {
low = mid + 1
}
}
}
return [-1, -1]
};
归纳起来上面几个问题要注意的就是：
- 初始值设置
- 循环的终止条件
- 返回值