二分查找 ||蟒蛇 ||資料結構和演算法

二分查找

二分搜尋是一種重複將搜尋空間一分為二的演算法。這種搜尋技術遵循分而治之的策略。每次迭代中搜尋空間總是減少一半。導致時間複雜度為 O(log(n))，其中 n 為元素數。

條件：陣列應該是排序的，但它們也可以應用於單調函數，我們需要找到單調遞增或單調遞減。

當我們需要以對數時間縮小搜尋空間時，它就有效。

我們使用兩個指針，左指針和右指針。取左右的平均值來找出中間元素。

現在，我們根據條件檢查應該將左右指針移到哪裡。

解決一個問題主要需要三個步驟：

1. 預處理： 如果輸入未排序，則對輸入進行排序。
2. 二分查找：使用兩個指標並找到中間部分來劃分搜尋空間，然後相應地選擇正確的一半。
3. 後處理：決定輸出。

二分搜尋演算法的優點 - 對於大數據，二分搜尋比線性搜尋更快，因為它每次將數組切成兩半，而不是逐一檢查每個元素。這使得它更快、更有效率。

限制：二分查找僅適用於已排序的數組，因此對於小型未排序數組效率不高，因為排序需要額外的時間。對於小型記憶體搜索，它的效果也不如線性搜索。

應用： 用於在排序數組中搜尋元素，時間複雜度為 O(log(n))，也可用於尋找數組中的最小或最大元素。

基本二分查找程式碼 -

程式碼

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

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

    # End Condition: left > right
    return -1

33。在旋轉排序數組中搜尋
給定可能旋轉後的陣列 nums 和整數目標，如果目標在 nums 中，則傳回目標索引，如果不在 nums 中，則傳回 -1。
您必須編寫一個運行時間複雜度為 O(log n) 的演算法。
範例1：
輸入：nums = [4,5,6,7,0,1,2]，目標 = 0
輸出：4

範例2：
輸入：nums = [4,5,6,7,0,1,2]，目標 = 3
輸出：-1

範例3：
輸入：nums = [1]，目標 = 0
輸出：-1

程式碼

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

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

    # End Condition: left > right
    return -1

1. 使用左右兩個指針，迭代直到它們重疊。
2. 找出中間元素。
3. 由於陣列已排序但已旋轉，我們不能簡單地將左側或右側的元素與中間的元素進行比較。
4. 首先，透過比較中指標與左指標或右指標來決定左部分或右部分排序。
5. 根據這個結論，相應地調整指針。

時間複雜度 - O(log(n))，因為搜尋空間在每次迭代中被分成兩半。
空間複雜度 - O(1)

單調遞增

162。求峰值元素

峰值元素是嚴格大於其鄰居的元素。
給定一個 0 索引的整數數組 nums，找到一個峰值元素，並傳回其索引。如果數組包含多個峰值，則傳回任意峰值的索引。
您可能會想像 nums[-1] = nums[n] = -∞。換句話說，一個元素總是被認為嚴格大於數組外部的鄰居。
您必須編寫一個在 O(log n) 時間內執行的演算法。

範例1：
輸入：nums = [1,2,3,1]
輸出：2
說明：3 是峰值元素，您的函數應傳回索引號 2。
範例2：
輸入：nums = [1,2,1,3,5,6,4]
輸出：5
說明：您的函數可以傳回索引號 1（峰值元素為 2）或索引號 5（峰值元素為 6）。

程式碼

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1

        while left <= right:

            mid = (left + right)//2
            print(f'left is {left},right is {right} and mid is {mid}')
            if nums[mid]==target:
                return mid

            if nums[mid] >= nums[left]:
                # if nums[mid]< target and target >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid -1
                else:
                    left = mid +1
            else:
                # if nums[mid] < target and target <= nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid +1
                else:
                    right = mid - 1

        return -1

1. 在此類問題中，我們需要透過比較中間的左側或右側元素來檢查峰值。
2. 這有助於確定圖表趨勢是向上還是向下。
3. 要找出最大值，請搜尋向上的斜率並探索正確的子空間。
4. 要找出最小值，請搜尋左側子空間

時間複雜度 - O(log(n))，因為搜尋空間在每次迭代中被分成兩半。
空間複雜度 - O(1)

以上是二分查找 ||蟒蛇 ||資料結構和演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！