Loop Control Statements in C Introduction to HTML How to use the Github API The image tag, anchor tag and the button tag Ordered and Unordered Lists in HTML The division tag HTML Forms Tables in HTML Introduction to C Programming Introduction to Python Varibles and Datatypes in Python Operators in Python Typecasting in Python Input and Output in Python If Else in Python Loops in Python Break, Continue and Pass in Python Python practice section 1 Lists in Python Tuple in Python

Binary Search in Python

Binary search is a sorting algorithm that helps to locate elements in a sorted array. Unlike linear search, Binary search does not work by comparing the key with every element of the array. At every step, it divides the array into two parts, discards one part, and then searches for the key in the other part. Hence, it is faster than linear search.

Algorithm

  1. Initially, we have a list of size N. In the first iteration, we will compare the key with the middle element i.e. the element at index (N/2). If arr[mid] = = key, we are done.
  2. Otherwise, If arr[mid] <= key, this means that the key is greater than the middle element. Since the list is sorted, we know that if the key is present, then it would be found from index mid+1 to N-1. For e.g. if the list is [1,2,3,5] and key=3, then arr[mid]=1 which is smaller than 3, so we know that if 3 is present, it would come after 2 in the list. Hence, we would search for the key between index mid+1 to N-1.
  3. Else if arr[mid] >= key, this means that the key is smaller than the middle element. Hence, we would search for the key between index 0 to mid-1.
  4. We will repeat the same procedure in that part of the list (i.e from 0 to mid-1 or mid+1 to N-1) by finding the middle element and then comparing with the key until the key is found or the list gets finished.

Iterative Approach


def binary_search(arr,key):
    low=0
    high=len(arr)-1

    while low <= high:
        mid=(high-low)//2
        if key==arr[mid]
            found_at=i
        if arr[i]>mid:
            low=mid+1
        else:
            high=mid-1

    # if we reach the end of the list and the key is not found, we return -1.
    return -1

arr=[1,2,3,4,5,6]
key=int(input("Enter key to search: "))

found_at=binary_search(arr,key)

if found_at!=-1:
print("Key found at index ",i)
else:
print("Key not found")
Output
Enter key to search: 3
Key found at index 2
Time Complexity : O(log n) where n is the size of the list.
Explanation : Suppose we have a list of size n. At first, we will compare the key with the element at (n/2)thindex. If it is greater than the key, then will compare the key with the (n/2-0)/2th element and if the middle element is smaller, then we will compare the key with the (n-n/2)/2th element and so on.
Hence, the key would be found in a maximum of log n comparisons i.e. if there are 16 elements in the list, then the key would be found in at most 4 comparisons. So, the time complexity of binary search will be O(log n).
Space Complexity : O(1) no additional space used.

Recursive Approach


def binary_search(arr,key,low,high):
    if low>high:
        return -1
    mid=(high-low)//2
    if key==arr[mid]:
        return i
    elif key>arr[mid]:
        return binary_search(arr,key,mid+1,high)
    else:
        return binary_search(arr,key,low,mid-1)

arr=[1,3,2,5,7]
key=int(input("Enter key to search: "))

found_at=binary_search(arr,key,0,len(arr)-1)

if found_at!=-1:
print("Key found at index ",i)
else:
print("Key not found")
Output
Enter key to search: 2
Key found at index 1
Time Complexity : O(log n) same as the iterative approach.
Space Complexity : O(n) for recursion stack.

Advantages and Disadvantages

Advantages :
  1. It is faster than linear search. Takes only O(log n) time.
Disadvantages :
  1. It works for sorted arrays only. So, if the array is not sorted, then to sort it we need to take O(n log n) extra time which will make it worse than linear search.