Demystifying Binary Search: A Powerful Algorithm For Efficient Searching

Jump To Right Section Show

In this tutorial, you will learn how the Binary Search sort works. Also, you will find working examples of Binary Search in Python.

Binary Search is a searching algorithm for finding an element’s position in a sorted array. In this approach, the element is always searched in the middle of a portion of an array. Binary search can be implemented only on a sorted list of items. If the elements are not sorted already, we need to sort them first.

Working Principle:

Select the middle element of the sorted collection.
If the middle element matches the desired value, the search is successful.
If the desired value is less than the middle element, discard the upper half of the collection.
If the desired value is greater than the middle element, discard the lower half of the collection.
Repeat the process on the remaining half until the value is found or the search interval becomes empty.

Binary Search Working

Binary Search Algorithm can be implemented in two ways which are discussed below.

Iterative Method
Recursive Method

The recursive method follows the divide and conquer approach. The general steps for both methods are discussed below.

The array in which searching is to be performed is:

Let x = 4 be the element to be searched.
Set two pointers low and high at the lowest and the highest positions respectively.
Find the middle element mid of the array ie. (arr[low + high]) / 2 = 6.
If x == mid, then return mid.Else, compare the element to be searched with m.
If x > mid, compare x with the middle element of the elements on the right side of mid. This is done by setting low to low = mid + 1.
Else, compare x with the middle element of the elements on the left side of mid. This is done by setting high to high = mid - 1.
Repeat steps 3 to 6 until low meets high.
x = 4 is found.

Binary Search Algorithm

Iteration Method


do until the pointers low and high meet each other.
    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > A[mid]) // x is on the right side
        low = mid + 1
    else                       // x is on the left side
        high = mid - 1

do until the pointers low and high meet each other.

mid = (low + high)/2

if (x == arr[mid])

return mid

else if (x > A[mid]) // x is on the right side

low = mid + 1

else // x is on the left side

high = mid - 1

Recursive Method


binarySearch(arr, x, low, high)
    if low > high
        return False 
    else
        mid = (low + high) / 2 
        if x == arr[mid]
            return mid
        else if x < data[mid]        // x is on the right side
            return binarySearch(arr, x, mid + 1, high)
        else                               // x is on the right side
            return binarySearch(arr, x, low, mid - 1)

binarySearch(arr, x, low, high)

if low > high

return False

else

mid = (low + high) / 2

if x == arr[mid]

return mid

else if x < data[mid] // x is on the right side

return binarySearch(arr, x, mid + 1, high)

else // x is on the right side

return binarySearch(arr, x, low, mid - 1)

Python, Java, C/C++ Examples (Iterative Method)


# Binary Search in python


def binarySearch(array, x, low, high):

    # Repeat until the pointers low and high meet each other
    while low <= high:

        mid = low + (high - low)//2

        if array[mid] == x:
            return mid

        elif array[mid] < x:
            low = mid + 1

        else:
            high = mid - 1

    return -1


array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

# Binary Search in python

def binarySearch(array, x, low, high):

# Repeat until the pointers low and high meet each other

while low <= high:

mid = low + (high - low)//2

if array[mid] == x:

return mid

elif array[mid] < x:

low = mid + 1

else:

high = mid - 1

return -1

array = [3, 4, 5, 6, 7, 8, 9]

x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:

print("Element is present at index " + str(result))

else:

print("Not found")

Python, Java, C/C++ Examples (Recursive Method)


# Binary Search in python


def binarySearch(array, x, low, high):

    if high >= low:

        mid = low + (high - low)//2

        # If found at mid, then return it
        if array[mid] == x:
            return mid

        # Search the left half
        elif array[mid] > x:
            return binarySearch(array, x, low, mid-1)

        # Search the right half
        else:
            return binarySearch(array, x, mid + 1, high)

    else:
        return -1


array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

# Binary Search in python

def binarySearch(array, x, low, high):

if high >= low:

mid = low + (high - low)//2

# If found at mid, then return it

if array[mid] == x:

return mid

# Search the left half

elif array[mid] > x:

return binarySearch(array, x, low, mid-1)

# Search the right half

else:

return binarySearch(array, x, mid + 1, high)

else:

return -1

array = [3, 4, 5, 6, 7, 8, 9]

x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:

print("Element is present at index " + str(result))

else:

print("Not found")

Key Advantages

Efficiency: Binary search operates on sorted data, allowing it to discard half of the remaining elements at each iteration. This logarithmic time complexity (O(log n)) ensures quick retrieval even for large datasets.
Versatility: Binary search can be applied to a wide range of data structures, including arrays, linked lists, and trees. As long as the collection is sorted, binary search can locate elements efficiently.
Guaranteed Accuracy: Due to its divide-and-conquer nature, binary search guarantees accurate results. If the target element is present, the algorithm will find it, providing a sense of reliability in various applications.

Applications of Binary Search

Searching in Databases: Binary search plays a vital role in database management systems, allowing for fast and efficient retrieval of records based on indexed attributes. It helps in optimizing search queries and improving overall performance.
Spell Checking: In spell-checking algorithms, a sorted dictionary can be efficiently searched using binary search to suggest alternative word options based on user input, thereby improving the accuracy of spelling correction.
Interval-based Problems: Binary search can be applied to solve interval-based problems, such as finding the intersection point between two intervals or identifying the first occurrence of a condition within a range.
Lower and Upper Bound Queries: Binary search is useful for finding the lower and upper bounds of a value in a sorted collection, enabling various statistical calculations and optimization algorithms.

Binary search is a powerful algorithm that revolutionizes the efficiency of searching operations. Its elegance lies in the ability to divide the search space in half at each step, leading to faster and more accurate results. With its wide range of applications, binary search has become an indispensable tool in computer science and programming, aiding in solving complex problems and optimizing performance.