題目說明

704. Binary Search
     給一個升序排列的整數陣列 nums 和一個目標值 target，請使用二分搜尋找到target的索引。如果不存在，回傳-1。

範例

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

程式碼

Python 解法

def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

Java 解法

class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
複雜度分析

• 時間複雜度：O(log n)，每次都砍半搜尋範圍。
• 空間複雜度：O(1)，只用指標變數。

Java vs Python 差異

• Python 用 // 取整數除法，Java打/會直接自動取整數。
• Java 寫 int mid = left + (right - left) / 2; 是為了避免 left+right 直接相加時可能溢位，Python 沒這問題。
• 兩邊迴圈條件都是 while left <= right，邊界不會漏掉。