Tag: binary search algorithm

Binary Search Algorithm Implementation with Python

Binary Search  is an algorithm that finds the position of a target in a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. Even though the idea is simple, implementing binary search correctly requires attention to some subtleties about its exit conditions and midpoint calculation, particularly if the values in the array are not all of the whole numbers in the range.

Source: https://en.wikipedia.org/wiki/Binary_search_algorithm

Below the binary search algorithm implementation  with python:


#Test_Binary_Search.py
Array=[-2,1,0,4,7,8,10,13,16,17, 21,30,45,100,150,160,191,200]
Target=201
n=len(Array)
def binarySearch(A,T):
L=0
R=n-1
while (L <= R):
m=int((L + R)/2)
if ( A[m] < T ):
L = m +1
elif (A[m] > T):
R = m-1
else:
print("Target is at %s:" % m)
return m
print("Target not found")
return "unsuccessful"

binarySearch(Array, Target)


In this example, the binary_search function takes a sorted list arr and an element x as input, and returns the index of the element if it is found, or -1 if it is not found. The function uses a binary search algorithm to search for the element in the list, by dividing the list into halves and comparing the element with the middle element of the list. If the element is greater than the middle element, it searches the right half of the list, and if it is less than the middle element, it searches the left half of the list. This process is repeated until the element is found or the list is exhausted.