二分查找集合

第一次出現某數的位置

• 如果沒找到，則傳回 -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;
}