Skip to content

LeetCode: 704-Binary Search 解題紀錄

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 nums are unique.
  • nums is 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 complexityO(log n)
Space complexityO(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
        

References


Read More

Leave a Reply