Algorithm 演算法 - 線性搜尋系列 Binary Search 二元搜尋
Play this article
基礎概念
Binary Search 的概念類似 Quick Sort 中的概念。Binary Search 需要仰賴已經排序好的資料,所以雖然搜尋的效率比線性搜尋來得高,但是刪減資料都會需要耗費另外的成本做排序。 而其實做方式有兩種:Iteration 和 Recursion。
Time Complexity:
- Best:
O(1)
- Average:
O(log n)
- Worst:
O(log n)
Space Complexity: O(1)
實作
Python
Iteration
def binarySearch(arr, l, r, x):
while l <= r:
mid = l + (r - l) // 2
# Check if x is present at mid
if arr[mid] == x:
return mid
# If x is greater, ignore left half
elif arr[mid] < x:
l = mid + 1
# If x is smaller, ignore right half
else:
r = mid - 1
# If we reach here, then the element
# was not present
return -1
Recursion
def binarySearch(arr, l, r, x):
# Check base case
if r >= l:
mid = l + (r - l) // 2
# If element is present at the middle itself
if arr[mid] == x:
return mid
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1