# 基礎概念

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
``````