# Binary Search

Section 1: Search in python, binary search

Binary Search can only be applied to a sorted list. If the list is not sorted, add the time complexity of sorting to that of binary sort to determine the total complexity.

• Divide the list into two halves (left, center element, right)
• If element we are searching for is center element, stop
• If element is greater than center element, divide right half of list and repeat the steps
• If element is less than center element, divide left half of list and repeat the steps

Eg: Array 1 2 3 4 5 6 7 8 9 Find 1

Scan 1: Middle:1; 1<5 > Array: 1,2,3,4

Scan 2: Middle:2; 1<2 > Array: 1

Scan 3: Middle:1; 1=1 > Stop

Recurrence T(n) = T(n/2) + c T(n/2) = T(n/4)+c

• T(n) = O(logn)
##### Implementation in python
``````#Note: Binary search only works when the list is sorted

def bsearch (seq, v, l, r):
if (r-l == 0):
return(False) #element not present

mid = (l+r)//2 #finding the middle element

if(v == seq[mid]): #if sequence equal to the middle element return true
return (True)

if (v < seq[mid]):
return (bsearch(seq,v,l,mid)) #search left half

else:
return (bsearch(seq,v,mid+1,r)) #search right half
``````

If you are stuck at any point or have any doubts, drop a message here

Published by in search and tagged algorithms, data structures, python and search using 209 words.