算法系列之二分查詢
二分查詢也稱折半查詢（Binary Search），二分查詢針對的是有序的線性表，並且線性表要採用順序儲存結構，滿足這個條件的就是陣列這種結構了。
查詢過程
首先，假設表中元素是按升序排列，將表中間位置的值與查詢目標值字比較，如果兩者相等，則查詢成功；否則利用中間位置將表分成前、後兩個子表，如果中間位置的值大於查詢關鍵字，則進一步查詢前一子表，否則進一步查詢後一子表。重複以上過程，直到找到滿足條件的記錄，使查詢成功，或直到子表不存在為止，此時查詢不成功。 - 百度百科
簡單二分查詢
簡單的二分查詢, 只要查到等於目標值的索引, 程式碼非常直接簡單
function bSearch(arr, target) {
let left = 0 //左指標
let right = arr.length - 1 //右指標
while (left <= right) {
let mid = (right - left) >> 1 + left
if (arr[mid] === target) {
return mid
} else if (arr[mid] < target) {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
複製程式碼
三個容易出錯的地方
-
迴圈退出條件，注意是
left<=right，而不是left < right -
mid的取值
實際上，
mid=(left+right)/2這種寫法是有問題的。因為如果left和right比較大的話，兩者之 和就有可能會溢位。改進的方法是將mid的計算方式寫成left+(right-left)/2。更進一步，如果 要持效能優化到扱致的話，我們可以將這裡的除以2操作轉化成位運算left+((right-left)>>1) -
left和right的更新
left=mid+1,right=mid-1。注意這裡的+1和-1 ,如果直接寫成left=mid或者right=mid , 就可能會發生死迴圈。比如，當right=k , left=k時，如果a[k]不等於target, 就會導致死迴圈。
二分查詢的變形
上面的簡單二分查詢是有序且不重複的陣列，我們現在來考察有序但是有重複資料的陣列 我們來看看四個變形問題
1. 查詢第一個等於目標值的元素索引
function bSearch1(arr, target) {
let left = 0
let right = arr.length - 1
while (left <= right) {
let mid = (right - left) >> 1 + left
if (arr[mid] === target) {
if (mid === 0 || arr[mid - 1] !== target) {
return mid
} else {
right = mid - 1
}
} else if (arr[mid] < target) {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
複製程式碼
注意現在數組裡面有重複的元素，所以當滿足arr[mid] === target
, mid不一定是第一個等於目標值的元素, 因此還需要一個條件分支判斷mid === 0 || arr[mid - 1] !== target
， 如果mid是0，那麼是第一個元素，肯定滿足條件，或者當前位置的前一個元素不等於目標值，那麼這個位置一定就是我們要找第一個等於目標值的元素的索引
如果不滿足這個條件，說明這個位置前面還有等於目標值的元素，那麼需要更新右邊的指標high = mid - 1
;
變形1理解了，後面的三個變形問題也是同樣的思路, 聰明的你肯定可以舉一反三
2. 查詢最後一個等於目標值的元素索引
function bSearch2(arr, target) {
let left = 0
let right = arr.length - 1
while (left <= right) {
let mid = (right - left) >> 1 + left
if (arr[mid] === target) {
if (mid === arr.length - 1 || arr[mid + 1] !== target) {
return mid
} else {
left = mid + 1
}
} else if (arr[mid] < target) {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
複製程式碼
3. 查詢第一個大於等於目標值的元素索引
function bSearch3(arr, target) {
let left = 0
let right = arr.length - 1
while (left <= right) {
let mid = (right - left) >> 1 + left
if (arr[mid] >= target) {
if (mid === 0 || arr[mid - 1] < target) {
return mid
} else {
right = mid - 1
}
} else {
left = mid + 1
}
}
}
複製程式碼
4. 查詢最後一個小於等於目標值的元素索引
function bSearch4(arr, target) {
let left = 0
let right = arr.length - 1
while (left <= right) {
let mid = (right - left) >> 1 + left
if (arr[mid] <= target) {
if (mid === arr.length - 1 || arr[mid + 1] > target) {
return mid
} else {
left = mid + 1
}
} else {
right = mid - 1
}
}
}
複製程式碼
leetcode相關題解
最後來看看leetcode的33題
題目描述：
假設按照升序排序的陣列在預先未知的某個點上進行了旋轉。 ( 例如，陣列 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。 搜尋一個給定的目標值，如果陣列中存在這個目標值，則返回它的索引，否則返回 -1 。 你可以假設陣列中不存在重複的元素。 你的演算法時間複雜度必須是 O(log n) 級別。
示例 1:
輸入: nums = [4,5,6,7,0,1,2], target = 0 輸出: 4
示例 2:
輸入: nums = [4,5,6,7,0,1,2], target = 3 輸出: -1 搜尋旋轉排序陣列, 要求時間複雜度是O(logn)
解題思路：
將陣列一分為二，其中一定有一個是有序的，另一個可能是有序，也能是部分有序。 此時有序部分用二分法查詢。無序部分再一分為二，其中一個一定有序，另一個可能有序，可能無序。就這樣迴圈直到找到目標值或者左邊界超出右邊界，退出迴圈
規律： 中間值比最右值小，則右半部有序遞增 中間值比最右值大，則左半部有序遞增
程式碼
function search(nums, target) {
let left = 0
let right = nums.length - 1
let mid
while (left <= right) {
mid = left + ((right - left) >> 1) // 注意位運算子打括號
if (nums[mid] == target) {
return mid
}
//右半部有序遞增
if (nums[mid] < nums[right]) {
if (nums[right] >= target && nums[mid] < target) {
left = mid + 1
} else {
right = mid - 1
}
} else {
if (nums[left] <= target && nums[mid] > target) {
right = mid - 1
} else {
left = mid + 1
}
}
}
return -1
}
複製程式碼
這個演算法也可以用遞迴實現，我用遞迴寫的程式碼在leetcode上通不過，老是報棧溢位錯誤，所以我這裡就不貼了，有興趣的可以嘗試寫一下遞迴程式碼