Binary search

Search a sorted or non-sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty

image source: geeksforgeeks

code:

arr=[i for i in range(0,23)]
#arr=[9,8,7,6,5,4,3,2,1,0]
element=3
def binary_search(arr,element):
flag = 0
arr1 = arr[:]
arr1.sort()
if (arr1 != arr):
arr.sort()
else:
flag = 1
pos = int(len(arr) / 2)
while arr[int(len(arr) / 2)] != element:
if len(arr) == 1 and arr != [element]:
print(-1)
break
if arr[int(len(arr) / 2)] > element:
arr = arr[:int(len(arr) / 2)]
pos = int(pos - (len(arr) / 2))
elif arr[int(len(arr) / 2)] < element:
arr = arr[int(len(arr) / 2):]
pos = int(pos + (len(arr) / 2))
else:
if flag:
print('element found at ',pos)
else:
print('element found at ',len(arr1)-1-pos)
print(arr)
binary_search(arr,element)

output:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
element found at 3

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sairam Penjarla

Sairam Penjarla

Looking for my next opportunity to make change in a BIG way