Binary Search Algorithm

A sorted array with 9 elements
  1. Divide the algorithm into two chunks and the least index is the left index, the highest index is the right index R and the middle index is calculated by the above formula floor((L+R)/2).
  2. Check if the value of the array in mid-index (array[M]) is equal to the searched value. If the value is found, return the mid-index.
  3. Consider the item to search, if the item is higher than the value of the array in mid-index (array[M]), move the left index to the right of mid-index.
  4. Consider the item to search, if the item is lesser than the value of the array in mid-index (array[M]), move the right index to the left of mid-index.
  5. Do the steps from 1 to 4 recursively until you find search value is equal to (array[M]).
  6. In some cases, the value you search may not be found in the array. At that time, stop searching when the left-index L is greater than the right-index R (L > R).
  • value = array[M]
  • value < array[M]
  • value > array[M]
import math
def search(val, arr ):
n = len(arr)
l = 0
r = n-1
while l<=r:
m = math.floor((l+r)/2)
if val==arr[m]:
return m
elif val<arr[m]:
r = m-1
elif val>arr[m]:
l = m+1
return "not found"
print(search(4, [0, 1, 2, 3, 4]))

--

--

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