[[Outcome 1 - Programming#12. algorithms for sorting and searching, including|U3 - AOS1 - KK12]]
***Binary Search*** is a [searching algorithm](https://www.geeksforgeeks.org/dsa/searching-algorithms/) that operates on a sorted or monotonic search space, repeatedly dividing it into halves to find a target value or optimal answer in logarithmic time O(log N).
### Conditions to apply Binary Search Algorithm in a Data Structure
- The data structure must be sorted.
- Access to any element of the data structure should take constant time.
### Binary Search Algorithm
- Divide the search space into two halves by ***finding the middle index "mid"***.
- Compare the middle of the search space with the ***key***.
- If the ***key*** is found at middle, the process is terminated.
- If the ***key*** is not found at middle, choose which half will be used as the next search space.
****->**** If the ***key*** is smaller than the middle, then the ***left*** side is used for next search.
-> If the ***key*** is larger than the middle, then the ***right*** side is used for next search.
- This process is continued until the key is found or the total search space is exhausted.
### ***How does Binary Search Algorithm work?***
To understand the working of binary search, consider the following illustration:
***Consider an array*** arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}***, and the*** target = 23.
![[image-7 1.png]]
![[image-8 1.png]]
![[image-9 1.png]]
![[image-10 1.png]]
```python
def binarySearch(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = low + (high - low) // 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:
low = mid + 1
# If x is smaller, ignore right half
else:
high = mid - 1
# If we reach here, then the element
# was not present
return -1
if __name__ == '__main__':
arr = [2, 3, 4, 10, 40]
x = 10
result = binarySearch(arr, x)
if result != -1:
print("Element is present at index", result)
else:
print("Element is not present in array")
```