LeetCode 解題練習：Binary Search

 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/binary-search/

中文描述

給定一個由小排到大的整數陣列 nums ，與一個整數 target，請在陣列中尋找 target 所在的索引位置。若找不到，請傳回 -1。必須用演算法時間複雜度為 O(log n) 的方法來解。

範例一：

輸入  nums = [1, 2, 3, 4, 5, 6, 7], target = 5

輸出 4

因為 5 在陣列 nums 索引位置 4。

範例二：

輸入  nums = [1, 2, 3, 4, 5, 6, 7], target = 8

輸出 -1

因為 8 不在陣列 nums 裡。

解法一：

二分搜尋法的演算法如下：

• 設定 left = 0, right = 陣列長度 - 1。
• 當 left <= right 時
• middle = (left + right) / 2。
• 判斷 target 與 nums[middle] 的大小關係。
• 若相等，回傳 middle。
• 若 nums[middle] 大於 target，right = middle - 1。
• 若 nums[middle] 小於 target，left = middle  + 1。
• 若 left > right 結束迴圈時，回傳 -1。

可參考下圖動畫說明：

Python Code

class Solution:

    def search(self, nums: List[int], target: int) -> int:

        left = 0

        right = len(nums) - 1

        while left <= right:

            middle = (left + right) // 2

            if nums[middle] == target:

                return middle

            elif nums[middle] > target:

                right = middle - 1

            else:

                left = middle + 1

       

        return -1