704. Binary Search

leetcode

前言

最近比較少在接觸電腦這一塊，因為準備升學所以課業繁忙，不過在這之下我還是依然對資工這一塊抱有興趣，所以我想趁我還沒全部忘掉之前，把之前練過的leetcode題目做一下筆記，讓我明年可以更快走回這條軌道。

題目

image alt
看起來他給了我們一個陣列，並且已經排序好了，接著我們需要找出給定的值在陣列中的第幾項，若陣列中沒有那一項東西就回傳’-1’，
而題目有要求時間複雜度要是O(log n)，所以二元搜尋法就非常適合囉。

解題

首先我們必須寫一次二元搜尋:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binary(nums):
            low = 0
            high = len(nums) - 1
            while low <= high:
                mid = (low + high) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] < target:
                    low = mid + 1
                else: 
                    high = mid - 1
            return -1 #找不到n
        return binary(nums)

為了讓我好複習，我還是講解一下好了，二元搜尋就是每次搜尋都對折，看質比中間的大或小，再對折，直到找到為止。

詳細介紹