【專論】Binary Search 到底該不該套模板來解題？

★ 付費 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 就會代表可行解的範圍：

278. First Bad Version