Description
給定一個升序排列的整數陣列
nums和一個目標值target，在陣列中搜尋target。如果存在回傳其索引，否則回傳-1。
Example:
Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4
Intuition#
已排序陣列中，每次比較中間元素就能排除一半的搜尋空間。
- 經典的二分搜尋：比較
mid與target - 相等則找到；
target較大則搜尋右半部；target較小則搜尋左半部
Approaches#
1: Linear Scan#
- 概念: 逐一掃描陣列找目標值
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
Linear Scan 程式碼
class Solution {
fun search(nums: IntArray, target: Int): Int {
for (i in nums.indices) {
if (nums[i] == target) return i
}
return -1
}
}⭐2: Binary Search#
- 概念: 維護 left 和 right 指標，每次取中間值比較，縮小搜尋範圍
- 時間複雜度:
O(log n) - 空間複雜度:
O(1)
class Solution {
fun search(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size - 1
while (left <= right) {
val mid = left + (right - left) / 2
when {
nums[mid] == target -> return mid
nums[mid] < target -> left = mid + 1
else -> right = mid - 1
}
}
return -1
}
}使用
left + (right - left) / 2而非(left + right) / 2來避免整數溢位。
🔑 Takeaways#
- Pattern: 標準二分搜尋模板
- 關鍵技巧: 注意迴圈條件
left <= right（閉區間）與left < right（半開區間）的差異，兩種寫法對應不同的邊界更新方式