转载

二分查找大集合（妈妈再也不用担心我的二分查找了）

什么是二分查找就不多说了。

有时经常会碰到类似于从一个有序数组中找到元素第一次出现的位置，求一个有序数组中小于某元素的个数，将一个元素插入一个有序数组中，等等这样的需求。比如 leetcode 315. Count of Smaller Numbers After Self 这道题用二分查找来解，就需要维护一个有序数组，不断往数组中添加元素。这样，传统的 "从一个有序数组中求一个元素的位置，有则返回，没有则返回 -1"，就需要变一下型了。

当然这完全可以用传统的二分查找，找到一个相对来说 "比较正确" 的位置，然后从这个位置向左向右扩展，完全可以，而且复杂度也基本是一样的，不过这样的实现太 ugly 了。

为了以后能不用每次遇到二分查找就要推下解，特记录如下，妈妈再也不用担心我的二分查找了。

第一次出现某数的位置

如果没找到，则返回 -1
可应对数据重复或者不重复两种情况
a 数组需正序排列

二分代码：

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。下同。

测试程序：

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。

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 进行大小对比。

测试程序：

function _binarySearch(a, target) {   for (var i = 0, len = a.length; i < len; i++) {     if (a[i] === target && a[i + 1] !== target)       return i;      if (a[i] > target)       return -1;   }    return -1; }

刚好比某数大的元素位置

a 数组需正序排列
如果所有数都比 target 小，则返回 a.length

跟求最后一次出现某数的位置类似。

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 start; }

如 return 的数等于数组的长度，则表示数组内所有元素都比 target 元素小。

测试程序：

function _binarySearch(a, target) {   for (var i = 0, len = a.length; i < len; i++) {     if (a[i] > target)       return i;   }    return a.length; }

刚好比某数小的元素位置

a 数组需正序排列
如数组所有元素都比 target 大，则返回 -1

代码：

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 end; }

如果 return -1，则表示数组中没有比 target 元素小的元素了（只能去找索引值为-1的元素了），这时要特别注意需要特判。

测试程序：

function _binarySearch(a, target) {   for (var i = a.length; i--; ) {     if (a[i] < target)       return i;   }    return -1; }

总结

暂时只想到这四种应用场景。

测试程序的测试用例：

for (var i = 0; i < 1000; i++) { // 1000 组数据   var len = ~~(Math.random() * 500); // 数组长度 0-500   var a = [];   for (var j = 0; j < len; j++)      a.push(~~(Math.random() * 500)); // 数组元素大小 0-500    a.sort(function(a, b) {return a - b}); // sort    var target = ~~(Math.random() * 500); // target 元素    var ans1 = binarySearch(a, target);   var ans2 = _binarySearch(a, target);    if (ans1 === ans2)     console.log('ok');   else      alert('error!'); }

正文到此结束