題目連結: https://leetcode.com/problems/binary-search/
參考解法: https://leetcode.com/problems/binary-search/discuss/423162/Binary-Search-101
解法一:
func search(_ nums: [Int], _ target: Int) -> Int {
if nums.count == 0 { return -1 }
var left = 0
var right = nums.count - 1
while left <= right {
let mid = (left + right) / 2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
解法二:
func search(_ nums: [Int], _ target: Int) -> Int {
if nums.count == 0 { return -1 }
var left = 0
var right = nums.count - 1
while left < right {
let mid = left + (right - left + 1) / 2
if nums[mid] > target {
right = mid - 1
} else {
left = mid
}
}
return nums[left] == target ? left : -1
}
Rule of thumb when it comes to binary search: (Note: below is from Ref)
- Include ALL possible answers when initialize
lo
&hi
- Don’t overflow the
mid
calculation - Shrink boundary using a logic that will exclude mid
- Avoid infinity loop by picking the correct
mid
and shrinking logic - Always think of the case when there are 2 elements left
Ref: https://leetcode.com/problems/binary-search/discuss/423162/Binary-Search-101