（如果觉得楼主的文章对你有帮助，请关注楼主的 Github https://github.com/hanzichi）
什么是二分查找就不多说了。
有时经常会碰到类似于从一个有序数组中找到元素第一次出现的位置，求一个有序数组中小于某元素的个数，将一个元素插入一个有序数组中，等等这样的需求。比如 leetcode 315. Count of Smaller Numbers After Self 这道题用二分查找来解，就需要维护一个有序数组，不断往数组中添加元素。这样，传统的 “从一个有序数组中求一个元素的位置，有则返回，没有则返回 -1″，就需要变一下型了。
当然这完全可以用传统的二分查找，找到一个相对来说 “比较正确” 的位置，然后从这个位置向左向右扩展，完全可以，而且复杂度也基本是一样的，不过这样的实现太 ugly 了。
为了以后能不用每次遇到二分查找就要推下解，特记录如下，妈妈再也不用担心我的二分查找了。
第一次出现某数的位置
- 如果没找到，则返回 -1
- 可应对数据重复或者不重复两种情况
- a 数组需正序排列
二分代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
function binarySearch(a, target) { var start = 0 , end = a.length - 1; while(start <= end) { var mid = ~~((start + end) >> 1); if (a[mid] >= target) end = mid - 1; else start = mid + 1; } return a[start] === target ? start : -1; } |
start 的最终结果永远比 end 大 1。下同。
测试程序：
|
1 2 3 4 5 6 7 8 9 10 11 |
function _binarySearch(a, target) { for (var i = 0, len = a.length; i < len; i++) { if (a[i] === target) return i; if (a[i] > target) return -1; } return -1; } |
最后一次出现某数的位置
- 如果没找到，返回-1
- 可应对数据重复或者不重复两种情况（如果数据不重复也可用前者）
- a 数组需正序排列
换个思路，求有序数组中最后一次出现某数的位置，也就是求 “该数+1″（不管它在不在数列中） 第一次出现的位置 – 1。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
function binarySearch(a, target) { target += 1; var start = 0 , end = a.length - 1; while(start <= end) { var mid = ~~((start + end) >> 1); if (a[mid] >= target) end = mid - 1; else start = mid + 1; } return a[end] === target - 1 ? end : -1; } |
这里要注意的是找到的 end 索引可能是 -1，但是因为数组是特殊的对象，所以 a[“-1”] 返回 undefined，正是利用了这个 hack，使得程序可以一行返回。同时要注意 target 在函数最开始已经自增过，所以需和 target-1 进行大小对比。
测试程序：
|
1 2 3 4 5 6 7 8 9 10 11 |
function _binarySearch(a, target) { for (var i = 0, len = a.length; i < len; i++) { if (a[i] === target && a[i + 1"> === target && a[i + 1会碰到类似于从一个有序数组中找到元素第一次出现的位置，求一个有序数组中小于某元素的个数，将一个元素插入一个有序数组中，等等这样的需求。比如 leetcode 315. Count of Smaller Numbers After Self 这道题用二分查找来解，就需要维护一个有序数组，不断往数组中添加元素。这样，传统的 “从一个有序数组中求一个元素的位置，有则返回，没有则返回 -1″，就需要变一下型了。
当然这完全可以用传统的二分查找，找到一个相对来说 “比较正确” 的位置，然后从这个位置向左向右扩展，完全可以，而且复杂度也基本是一样的，不过这样的实现太 ugly 了。 为了以后能不用每次遇到二分查找就要推下解，特记录如下，妈妈再也不用担心我的二分查找了。 第一次出现某数的位置
二分代码：
start 的最终结果永远比 end 大 1。下同。 测试程序：
最后一次出现某数的位置
换个思路，求有序数组中最后一次出现某数的位置，也就是求 “该数+1″（不管它在不在数列中） 第一次出现的位置 – 1。
这里要注意的是找到的 end 索引可能是 -1，但是因为数组是特殊的对象，所以 a[“-1”] 返回 undefined，正是利用了这个 hack，使得程序可以一行返回。同时要注意 target 在函数最开始已经自增过，所以需和 target-1 进行大小对比。 测试程序：
|
