Algorithm: Binary Search

Binary Search is one of the most fundamental and useful algorithms in Computer Science. It describes the process of searching for a specific value in an ordered collection.

it works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed down the possible locations to just one.

Time complexity - O(log n)

The terminology used in Binary Search:

• Target - the value that you are searching for

• Index - the current location that you are searching

• Left, Right - the indices from which we use to maintain our search Space

• Mid - the index that we use to apply a condition to determine if we should search left or right

A Binary Search Algorithm can be implemented in the following two ways

1. Iterative Method

2. Recursive Method

Figure 1: Example of Binary Search Algorithm

example problem:

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

python3 code snippet: Iterative Method

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1                        
            else:
                right = mid - 1

        return -1

python3 code snippet: Recursive Method

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binSearch(left: int, right: int) -> int:
            if left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] < target:
                    return binSearch(mid+1,right)                      
                else:
                    return binSearch(left,mid-1)
            else:
                return -1
            
        return binSearch(0,len(nums)-1)

Advantages

• Binary search is faster than linear search.

• relatively simple to implement and easy to understand.

• can be used on both sorted arrays and sorted linked lists, making it a flexible algorithm.

Disadvantages

• We need to have the array to be sorted which requires additional time complexity.

• Can be less efficient than other algorithms, such as hash tables, for searching very large datasets that do not fit in memory.