1、Binary Search算法簡介

二分查找，它的時(shí)間復(fù)雜度是 O(logn)。 ?其核心思想有點(diǎn)類似分治思想。

即每次都通過跟區(qū)間中的中間元素對比，將待查找的區(qū)間縮小為一半，直到找到要查找的元素，或者區(qū)間被縮小為 0。

但是二分查找的代碼實(shí)現(xiàn)比較容易寫錯(cuò)。你需要著重掌握它的三個(gè)容易出錯(cuò)的地方： 循環(huán)退出條件、mid 的取值，low 和 high 的更新 。 ?

二分查找雖然性能比較優(yōu)秀，但應(yīng)用場景也比較有限。 底層必須依賴數(shù)組 ，并且還要求 數(shù)據(jù)是有序 的。對于較小規(guī)模的數(shù)據(jù)查找，我們直接使用順序遍歷就可以了，二分查找的優(yōu)勢并不明顯。二分查找更適合處理 靜態(tài)數(shù)據(jù) ，也就是沒有頻繁的數(shù)據(jù)插入、刪除操作。

2、代碼詳解

            
              class Solution:
    def bsearch(self, nums, target):
        """Binary search of a target in a sorted array
        without duplicates. If such a target does not exist,
        return -1, othewise, return its index.
        """
        left, right = 0, len(nums)-1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

s = Solution()
a = [1,3,5,6,7,9,11]
print(s.bsearch(a, 7))
            
          

?