BINARY SEARCH

Binary Search

• Binary Search is the most popular search algorithm and it is also efficient.
• If all the names in the world are written down together in order and you want to search for a position of a specific name then Binary Search will accomplish this in a maximum 35 iterations.
• Binary Search works only on a sorted array. If we want to use binary search on a collection, then first the collection must be in sorted.
• The Runtime complexity of a Binary Search is O(log n)

How It Works

• Before beginning the Binary Search first we have to find the start and end of the range.
• Binary Search begins by comparing the middle element of the range.
• If the middle element is the same as the target element (target element meant the element that we want to search in the range), then it returns the index of that element.
• If the middle element did not match the target element then it divides the range into the two halves. The first half consist of the first element to the middle element and the second half consist of the element next to the middle element to the last element.
• If the middle element did not match the target element then it compares the middle element with the target element.
• If the target element is greater than the middle element then we have to search in the second half by changing the start to middle+1
• If the target element is smaller than the middle element then we have to search in the first half by changing the end to the middle-1.
• Repeat this procedure recursively until start <= end. In any iterations, if we get the target element is equal to the middle element, then we return the index of the middle element. if we did not get the target element in the range then we return the -1.

A little demo on how Binary Search works

Here is a sample of what the binary search code might look like

def BinarySearch(arr, target):
    start = 0       # first element of the range
    end = len(arr) - 1      # last element of the range  
    while start <= end:
        mid = int((start + end) / 2)
        if arr[mid] == target:  # check if target elemtn  is equal to mid if yes … then return mid
            return mid
        if arr[mid] < target:   # if number target element is greater than mid … update start value to mid + 1 and recalculate mid value
            start = mid + 1
        if arr[mid] > target:   # if number target element is less than mid … update end value to mid - 1 and recalculate mid value
            end = mid - 1
    return -1