二分查找集合

第一次出现某数的位置

• 如果没找到，则返回 -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;
}