Binary Search use case.
In computer science binary search is a search algorithm that finds the position of a target element within a sorted array. Binary search is also called half-interval search, logarithmic search, or binary chop. Binary search compares the target element's value to the middle element of the array (list). If elements are not equal, the half in which the target cannot belong is eliminated and the search continues on the remaining half, also taking the middle element to compare to the target value.
Python Knowledge Base: Make coding great again.
- Updated:
2024-07-26 by Andrey BRATUS, Senior Data Analyst.
Binary Search Python code - Iterative Method:
Binary Search Python code - Recursive Method:
The process goes on until the target element is found.
If the search finishes with empty remaining half, the target is not in the array.
Binary Search Algorithm can have 2 implementations:
- Iterative Method.
- Recursive Method.
def binary_Search(array, x, low, high):
# Repeating until the pointers low and high meet
while low <= high:
mid = low + (high - low)//2
if array[mid] == x:
return mid
elif array[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
array = [3, 5, 4, 0, 12, 11]
x = 12
result = binary_Search(array, x, 0, len(array)-1)
if(result == -1):
print("Searched element not found")
else:
print("Searched element found at index: ", result)
OUT: Searched element found at index: 4
def binary_Search(array, x, low, high):
if high >= low:
mid = low + (high - low)//2
# If found at mid, then return it
if array[mid] == x:
return mid
# Search the left half
elif array[mid] > x:
return binary_Search(array, x, low, mid-1)
# Search the right half
else:
return binary_Search(array, x, mid + 1, high)
else:
return -1
array = [3, 5, 4, 0, 12, 11]
x = 12
result = binary_Search(array, x, 0, len(array)-1)
if(result == -1):
print("Searched element not found")
else:
print("Searched element found at index: ", result)
OUT: Searched element found at index: 4