★ 付費 Premium 專享 ★
↑看個小廣告，支持好內容↑
二分搜尋 (Binary Search) 是優於線性搜尋的演算法，相較於一個一個找，二分法總是奉行「中央一刀切」，每次都將查找的範圍縮小一半，假設我們要在 長度＝7 的陣列找數字 99，線性搜尋會很衰地連找七次才找到，但二分搜尋可以確保在三次以內就搞定。這就是O(n)、O(logn)的差別：
很顯然，二分法的大前提是只適用於排序好的資料。由於思路單純固定，有人會將二分搜尋的步驟模板化，用套版公式解題；但也有人認為應該先了解題意，不要死背解法，到底該聽哪一邊的呢？
先說結論，我認為主要的模板是可以記的，但是各題目要求的輸出、邊界狀況不同，這就要酌情滾動式調整了。
// 0.確認搜尋策略
// 1.界定搜尋範圍
// 2.當兩者範圍重疊，即離開迴圈
while(left<right){
let mid=left+Math.floor((right-left)/2);
// 3A.中間項之運算仍小於目標，左半邊都不用找了
if(運算結果<target){
left=mid+1;
// 3B.中間項之運算不小於目標，則成為新的右端點
}else{
right=mid;
}
}
// 4.檢查邊界條件、輸出結果
來找幾個經典題試試，在陣列中搜尋項目時，left,right 代表首項和末項：
704. Binary Search
輸出結果：index或-1(若該數字不存在)
搜尋策略：首個不小於 target 的位置
// 1.界定搜尋範圍
let left=0, right=arr.length-1;
// 2.當兩者範圍重疊，即離開迴圈
while(left<right){
let mid=left+Math.floor((right-left)/2);
// 3A.中間項之運算仍小於目標，左半邊都不用找了
if(arr[mid]<target){
left=mid+1;
// 3B.中間項之運算不小於目標，則成為新的右端點
}else{
right=mid;
}
}
// 4.檢查該項是否等同target，若無則輸出-1
// nums=[3,4,8,10], target=8: 輸出 2
// nums=[3,4,8,10], target=9: 輸出 -1
return nums[left]==target? left: -1;
35. Search Insert Position
輸出結果：index(表示數字出現或插入之處)
搜尋策略：首個不小於 target 的位置
// 1.界定搜尋範圍
let left=0, right=arr.length-1;
// 2.當兩者範圍重疊，即離開迴圈
while(left<right){
let mid=left+Math.floor((right-left)/2);
// 3A.中間項之運算仍小於目標，左半邊都不用找了
if(arr[mid]<target){
left=mid+1;
// 3B.中間項之運算不小於目標，則成為新的右端點
}else{
right=mid;
}
}
// 4.如果該項仍然小於target，則插入在陣列最後
// nums=[1,3,5,6], target=6: 輸出 3
// nums=[1,3,5,6], target=7: 輸出 4
return nums[left]>=target? left: left+1;
如果是猜數字或數學問題，left,right 就會代表可行解的範圍：
