Last Updated on 2022-03-26 by Clay
題目
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1
Constraints:
1 <= nums.length <= 104-104 < nums[i], target < 104- All the integers in
numsare unique. numsis sorted in ascending order.
題目給定一串排序過的數值陣列，並給予一個要找到的目標值。如果目標值存在於陣列，則回傳該目標值的索引（index）；如果目標值不存在於陣列，則回傳 -1。
解題思路
二元搜索（Binary Search）
題目底下煞有其事告訴你必須編寫一個時間複雜度為 O(log n) 的演算法，但題目名稱卻完全沒在演的，直接告訴你就是要用二元搜索法（Binary Search）XDDD
二元搜索法，實際上就是我們一開始就決定了要判斷的陣列左右邊界，接著直接取『中間值』，比方說 [1, 2, 3, 4, 5] 的陣列，其中間值就是 3。
那假設我們的目標值是 2 呢？那麼我們就會發現我們的中間值 3 太大了。於是我們縮減範圍，只考慮 [1, 2] 的陣列（因為 3 已經判斷過了、而比 3 大的都不可能是目標值）。
接著 (1 - 0) / 2 = 0，我們接著判斷索引值為 0 的 1，發現這個數字反而太小了…… 於是我們沒得選，只剩下 [2] 單個元素可以考慮。
這個方法的效率自然比直接一個個地遍歷搜索來得更好，畢竟在每次查找過後，都可以捨去一半左右的不匹配數值。
二元搜索複雜度
| Time complexity | O(log n) |
| Space complexity | O(1) |
二元搜索 C++ 範例程式碼
class Solution {
public:
int search(vector<int>& nums, int target) {
// Init
int left = 0;
int right = nums.size() - 1;
// Looking for the target
while (left <= right) {
int middle = left + (right-left) / 2;
if (nums[middle] > target) {
right = middle - 1;
}
else if (nums[middle] < target) {
left = middle + 1;
}
else {
return middle;
}
}
// If not found
return -1;
}
};二元搜索 Python 範例程式碼
class Solution:
def search(self, nums: List[int], target: int) -> int:
# Init
left = 0
right = len(nums) - 1
# Looking for the target
while (left <= right):
middle = left + (right-left) // 2
if nums[middle] > target:
right = middle - 1
elif nums[middle] < target:
left = middle + 1
else:
return middle
# If not found
return -1