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