The Magic of Binary Search Algorithm

Obaydur Rahman

Obaydur Rahman Full Stack Software Engineer

The Magic of Binary Search Algorithm

Introduction

Ever tried to find a word in a dictionary? How do you do it? You don't start from the first page and flip through every single page, right? Instead, you open it roughly in the middle and check if the word you're looking for is before or after that page. This is the essence of the Binary Search Algorithm.

Binary search is a method to quickly find a specific item in a sorted list. It works by looking at the middle element of the list and comparing it with the item you're searching for. If the middle element isn't the target, it decides whether to search in the left half or the right half of the list. This process repeats until the item is found or the list can no longer be split.

Binary Search in Action

Before we dive into the technical stuff, let's see how binary search works compared to linear search.

Linear search works by checking each element in the list one by one until it finds the target.

Let's click on a number from the list below to see how linear search finds it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

You see, it started from the first element and checked each one until it found the target. This takes time, especially if the list is long and the target is at very end or not present at all.

Binary search, on the other hand, is much faster. It divides the list in half with each step. Let's see how it works.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

You can see that it starts in the middle and checks if the target is greater or less than the middle element. Based on that, it decides which half to search next. This process continues until the target is found or the list can't be divided anymore.

This is the magic of binary search! It reduces the number of comparisons needed to find the target, making it much more efficient than linear search. The time complexity of binary search is O(log n), while linear search has a time complexity of O(n). This means that as the list grows larger, binary search becomes significantly faster than linear search.

Remember, binary search only works on sorted lists. If the list isn't sorted, you'll need to sort it first before using binary search.

Algorithm

Now that we understand how binary search works, let's look at the algorithm in detail.

The binary search algorithm can be implemented in two ways: iteratively and recursively. Both methods achieve the same result, but they differ in their approach.

Algorithm

Step 1: Find the middle element of the list.

Step 2: Compare the middle element with the target element.

Step 3: If the middle element is equal to the target element, then return the index of the middle element.

Step 4: If the middle element is greater than the target element, then search the left half of the list.

Step 5: If the middle element is less than the target element, then search the right half of the list.

Step 6: Repeat steps 1 to 5 until the target element is found or the list cannot be divided anymore.

Pseudocode

The binary search algorithm can be represented in pseudocode as follows:

FUNCTION binary_search(SORTED_LIST[], TARGET)
    SET LEFT TO 0
    SET RIGHT TO LENGTH(SORTED_LIST) - 1

    WHILE LEFT <= RIGHT DO
        SET MIDDLE TO (LEFT + RIGHT) / 2
        IF SORTED_LIST[MIDDLE] == TARGET THEN
            RETURN MIDDLE
        ELSE IF SORTED_LIST[MIDDLE] < TARGET THEN
            SET LEFT TO MIDDLE + 1
        ELSE
            SET RIGHT TO MIDDLE - 1
        END IF
    END WHILE

    RETURN -1
END FUNCTION

Implementation

Now, let's implement the binary search algorithm in various programming languages.

Binary Search using Iteration

function binarySearch(sortedList, target, left, right) {
    while (left <= right) {
        let middle = Math.floor((left + right) / 2);
        if (sortedList[middle] === target) {
            return middle;
        } else if (sortedList[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    return -1;
}

let sortedList = [1, 2, 3, 4, 5, 6, 7];
let target = 5;
let left = 0;
let right = sortedList.length - 1;
let index = binarySearch(sortedList, target, left, right);
if (index === -1) {
    console.log("Element not found");
} else {
    console.log("Element found at index " + index);
}

function binarySearch($sortedList, $target, $left, $right) {
    while ($left <= $right) {
        $middle = floor(($left + $right) / 2);
        if ($sortedList[$middle] === $target) {
            return $middle;
        } else if ($sortedList[$middle] < $target) {
            $left = $middle + 1;
        } else {
            $right = $middle - 1;
        }
    }

    return -1;
}

$sortedList = [1, 2, 3, 4, 5, 6, 7];
$target = 5;
$left = 0;
$right = count($sortedList) - 1;
$index = binarySearch($sortedList, $target, $left, $right);
if ($index === -1) {
    echo "Element not found";
} else {
    echo "Element found at index " . $index;
}

def binary_search(sorted_list, target, left, right):
    while left <= right:
        middle = (left + right) // 2
        if sorted_list[middle] == target:
            return middle
        elif sorted_list[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

sorted_list = [1, 2, 3, 4, 5, 6, 7]
target = 5
left = 0
right = len(sorted_list) - 1
index = binary_search(sorted_list, target, left, right)
if index == -1:
    print("Element not found")
else:
    print("Element found at index", index)

public class BinarySearch {
    public static int binarySearch(int[] sortedList, int target, int left, int right) {
        while (left <= right) {
            int middle = (left + right) / 2;
            if (sortedList[middle] == target) {
                return middle;
            } else if (sortedList[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] sortedList = {1, 2, 3, 4, 5, 6, 7};
        int target = 5;
        int left = 0;
        int right = sortedList.length - 1;
        int index = binarySearch(sortedList, target, left, right);
        if (index == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index " + index);
        }
    }
}

#include <stdio.h>

int binary_search(int sorted_list[], int target, int left, int right) {
    while (left <= right) {
        int middle = (left + right) / 2;
        if (sorted_list[middle] == target) {
            return middle;
        } else if (sorted_list[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    return -1;
}

int main() {
    int sorted_list[] = {1, 2, 3, 4, 5, 6, 7};
    int target = 5;
    int left = 0;
    int right = sizeof(sorted_list) / sizeof(sorted_list[0]) - 1;
    int index = binary_search(sorted_list, target, left, right);
    if (index == -1) {
        printf("Element not found\n");
    } else {
        printf("Element found at index %d\n", index);
    }
}

Binary Search using Recursion

function binarySearch(sortedList, target, left, right) {
    if (left > right) {
        return -1;
    }

    let middle = Math.floor((left + right) / 2);
    if (sortedList[middle] === target) {
        return middle;
    } else if (sortedList[middle] < target) {
        return binarySearch(sortedList, target, middle + 1, right);
    } else {
        return binarySearch(sortedList, target, left, middle - 1);
    }
}

let sortedList = [1, 2, 3, 4, 5, 6, 7];
let target = 5;
let left = 0;
let right = sortedList.length - 1;
let index = binarySearch(sortedList, target, left, right);
if (index === -1) {
    console.log("Element not found");
} else {
    console.log("Element found at index " + index);
}

function binarySearch($sortedList, $target, $left, $right) {
    if ($left > $right) {
        return -1;
    }

    $middle = floor(($left + $right) / 2);
    if ($sortedList[$middle] === $target) {
        return $middle;
    } else if ($sortedList[$middle] < $target) {
        return binarySearch($sortedList, $target, $middle + 1, $right);
    } else {
        return binarySearch($sortedList, $target, $left, $middle - 1);
    }
}

$sortedList = [1, 2, 3, 4, 5, 6, 7];
$target = 5;
$left = 0;
$right = count($sortedList) - 1;
$index = binarySearch($sortedList, $target, $left, $right);
if ($index === -1) {
    echo "Element not found";
} else {
    echo "Element found at index " . $index;
}

def binary_search(sorted_list, target, left, right):
    if left > right:
        return -1

    middle = (left + right) // 2
    if sorted_list[middle] == target:
        return middle
    elif sorted_list[middle] < target:
        return binary_search(sorted_list, target, middle + 1, right)
    else:
        return binary_search(sorted_list, target, left, middle - 1)

sorted_list = [1, 2, 3, 4, 5, 6, 7]
target = 5
left = 0
right = len(sorted_list) - 1
index = binary_search(sorted_list, target, left, right)
if index == -1:
    print("Element not found")
else:
    print("Element found at index", index)

public class BinarySearch {
    public static int binarySearch(int[] sortedList, int target, int left, int right) {
        if (left > right) {
            return -1;
        }

        int middle = (left + right) / 2;
        if (sortedList[middle] == target) {
            return middle;
        } else if (sortedList[middle] < target) {
            return binarySearch(sortedList, target, middle + 1, right);
        } else {
            return binarySearch(sortedList, target, left, middle - 1);
        }
    }

    public static void main(String[] args) {
        int[] sortedList = {1, 2, 3, 4, 5, 6, 7};
        int target = 5;
        int left = 0;
        int right = sortedList.length - 1;
        int index = binarySearch(sortedList, target, left, right);
        if (index == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index " + index);
        }
    }
}

#include <stdio.h>

int binary_search(int sorted_list[], int target, int left, int right) {
    if (left > right) {
        return -1;
    }

    int middle = (left + right) / 2;
    if (sorted_list[middle] == target) {
        return middle;
    } else if (sorted_list[middle] < target) {
        return binary_search(sorted_list, target, middle + 1, right);
    } else {
        return binary_search(sorted_list, target, left, middle - 1);
    }
}

int main() {
    int sorted_list[] = {1, 2, 3, 4, 5, 6, 7};
    int target = 5;
    int left = 0;
    int right = sizeof(sorted_list) / sizeof(sorted_list[0]) - 1;
    int index = binary_search(sorted_list, target, left, right);
    if (index == -1) {
        printf("Element not found\n");
    } else {
        printf("Element found at index %d\n", index);
    }
}

Performance Analysis

The performance of the binary search algorithm can be analyzed in terms of time and space complexity.

The time complexity of binary search is O(log n), where n is the number of elements in the list. This is because the algorithm divides the list in half with each step, leading to a logarithmic growth in the number of comparisons needed.

The space complexity is O(1) for the iterative version, as it uses a constant amount of space. The recursive version has a space complexity of O(log n) due to the call stack used for recursion.

CaseTime ComplexitySpace Complexity
BestO(1)O(1)
AverageO(log n)O(1)
WorstO(log n)O(1)

Conclusion

Binary search is a powerful algorithm that can significantly reduce the time it takes to find an element in a sorted list. By dividing the list in half with each step, it achieves a logarithmic time complexity, making it much faster than linear search for large datasets.