Aim:
To write a Python Program to perform binary search.
Algorithm:
1. Read the search element
2. Find the middle element in the sorted list
3. Compare the search element with the middle element
i. if both are matching, print element found
ii. else then check if the search element is smaller or larger than the middle element
4. If the search element is smaller than the middle element, then repeat steps 2 and 3 for the
left sublist of the middle element
5. If the search element is larger than the middle element, then repeat steps 2 and 3 for the
right sublist of the middle element
6. Repeat the process until the search element if found in the list
7. If element is not found, loop terminates
Program:
# Python code to implement iterative Binary Search.
# It returns location of x in given array arr
# if present, else returns -1
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
# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 4
# Function call
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print "Element is present at index % d" % result
else:
print "Element is not present in array"
Sample Output:
$python main.py Element is present at index 2