Binary Search

Binary Search

Binary Search is a method of searching an element in a sorted list of items. It follows the divide and conquer approach. The list is divided into two halves. The key(element to be searched) is compared with the middle element of list. If the element is found the index is returned, else, the element is searched in either of the sub-list until found or the last sub-list(only one element remaining) is visited.

Illustration:

BS.gif

Algorithm

1. Initialize the sorted list, set low=0 and high=length(list)-1
2. Set mid=low+(high-low)//2
3. Compare key with element at mid
4. If list[mid]==key, then return mid
5. Else if list[mid]>key, then low=low and high=mid-1
6. Repeat from 2 till list[mid]=key, else return= -1
7. Else low=mid+1 and high=high
8. Repeat from 2  till list[mid]=key, else return=-1
9. If return = -1, then print "Not found"
End

Time Complexity:

  • Worst Case: O(log n)
  • Average Case: O(log n)
  • Best Case: O(1)

Space Complexity: O(1)

def binarySearch (li, low, high, x): # Returns index of element in li if present, else -1

    if high >= low: 
        mid = low + (high - low) // 2

        if li[mid] == x:    #if element is present at mid
            return mid 

        elif li[mid] > x:  #If element is smaller than element at mid
            return binarySearch(li, low, mid-1, x)  # Element can only be present in left sub part of the li

        else: 
            return binarySearch(li, mid + 1, high, x)  #Else the element can only be present in right sub part of the li 

    else:  
        return -1 #Element not present in li


inp=input("Enter a sorted list: ").split()
li=[]
for i in inp:
    li.append(int(i))
x = int(input("Element to be Searched: "))

# Function call 
result = binarySearch(li, 0, len(li)-1, x) 

if result != -1: 
    print ("Element is present at index % d" % result) 
else: 
    print ("Element is not present in the list")