二分検索(Python)


1、Binary Searchアルゴリズムの概要
二分検索では,その時間的複雑さはO(logn)である.その核心思想は分治思想に似ている.
すなわち、検索対象の要素が見つかるまで、区間の中間要素と比較するたびに、検索対象の区間を半分に縮小したり、区間を0に縮小したりします.
しかし、二分検索のコード実装は書き間違えやすい.ループ終了条件、midの値、low、highの更新の3つのエラーを把握する必要があります. 
二分検索は性能は優れているが,応用シーンも限られている.最下位層は配列に依存し、データが秩序化されていることを求めなければならない.小規模なデータ検索では,順序を直接使用すればよいが,二分検索の利点は明らかではない.二分検索は、静的データの処理に適しています.つまり、頻繁なデータ挿入、削除操作はありません.
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))