Binary Search

by Aaron • 2/27/2025, 12:01:10 PM

根據維基

是一種在有序陣列中搜尋某一特定元素的搜尋演算法。搜尋過程從陣列的中間元素開始，如果中間元素正好是要搜尋的元素，則搜尋過程結束；如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中搜尋，而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。

根據搜尋區間又可以分成三種：

1. 左右封閉區間
2. 左封閉右開區間
3. 左開右封閉區間

根據不同的搜尋區間, 演算法的邊界條件就會有所不同。

1. 左右封閉區間

def binary_search(nums, target)
    left = 0
    right = nums.size - 1

    while left <= right # 為什麼是大於等於呢？
        mid = (left + right) / 2
        if nums[mid] == target
            return mid
        elsif nums[mid] > target
            right = mid - 1 # 為什麼是 mid - 1 呢？
        else
            left = mid + 1 # 為什麼是 mid + 1 呢？
        end
    end
    -1
end

• 問題 1:

  • 為什麼 left <= right 呢？
  • 答: 可以思考當 left = right 的時候, 還符合左右封閉區間的條件嗎？ (符合)

• 問題 2:

  • 為什麼是 right = mid - 1 呢？
  • 答: 因為 mid 已經不是 target 了, 如果 right = mid, 下一次的搜尋範圍就會包含 mid。

2. 左封閉右開區間

def binary_search(nums, target)
    left = 0
    right = nums.size

    while left < right # 為什麼是小於呢？
        mid = (left + right) / 2
        if nums[mid] == target
            return mid
        elsif nums[mid] > target
            right = mid # 為什麼是 mid 呢？
        else
            left = mid + 1 # 為什麼是 mid + 1 呢？
        end
    end
    -1
end

• 問題 1:

  • 為什麼 left < right 呢？
  • 答: 可以思考當 left = right 的時候, 還符合左封閉右開區間的條件嗎？ (不符合)

• 問題 2:

  • 為什麼是 right = mid 呢？
  • 答: 因為是右開。right = mid 時下一次的搜尋範圍並不會包含 mid。

• 問題 3:

  • 為什麼是 left = mid + 1 呢？
  • 答: 因為是左封閉。left = mid 時下一次的搜尋範圍會包含 mid, 但 mid 已確認不是 target 了。

3. 左開右封閉區間

def binary_search(nums, target)
    left = -1
    right = nums.size - 1

    while left < right
        mid = (left + right + 1) / 2
        if nums[mid] == target
            return mid
        elsif nums[mid] > target
            right = mid - 1
        else
            left = mid
        end
    end
    -1
end

Leetcode

• Find First and Last Position of Element in Sorted Array