Binary Search Using Python

By SRIJAN MAJUMDAR

In this project we will implement the binary search in an array using the python programming language.

The Binary Search is used to search an element from the array. The time complexity of the Binary Search is O(lgn) where n is the size of the array or the input size. It is the least time complexity to search an element and uses the divide and conquer algorithm in the sorted array. There are two approaches to implement the binary search, one is the recursive binary search, another one is the iterative binary search. The iterative binary search code is shown below:

The recursive Binary Search is shown below:

The recurrence relation for the binary search will be: T(n)={T(n/2) + 1; if n>1, 1;if n==1}. As the binary search searches the element in the left subarray or in the right subarray that is n/2 or n/2. Thus, the time complexity becomes T(n/2) plus with some constant c. Here, T(n) denotes the time complexity of the binary search. Since, here in the relation a=2,b=2,k=0,p=0. By, the master theorem, we get the time complexity as T(n) = O(lgn) which is the worst-case time complexity. 

Let us consider the example of the array(arr): [-35,-10,88,788,1034451] and let the element to be searched for be -10(key). By the algorithm, here start_index=0, end_index = 5-1 = 4, mid = 0 + (4-0)//2 = 2 so, (arr[2] > key) end becomes as end = mid - 1. Now end_index = 2-1 = 1 and mid = 0 + (1-0)//2 = 0 so,(arr[0]< key ) start becomes as start = mid + 1. Now start_index = 1 and mid = 1 +(1-1)//2 =1. Thus, arr[mid] = key we have to return mid which is 1. Therefore the element -10 is present in the array and the index returned is 1. Let us consider another example of the same array above but the element to be searched for is 80(key). Here, also start_index=0, end_index=5-1=4 and mid=0+(4-0)//2 = 2. So,(arr[2]>key) end index becomes as end_index=mid-1 =2-1=1. Mid becomes = 0 + (1-0)//2 =0 but arr[mid]