Binary Search Algorithm

Obaydur Rahman

Obaydur Rahman Full Stack Software Engineer

Binary Search Algorithm

Binary Search, also known as half-interval search, logarithmic search, or binary chop is a searching algorithm that is used to search data in a sorted list. It is a divide and conquer algorithm that reduces the search space by half at every step.

How does Binary Search work?

Let's imagine we have a book with 24 pages and you want to go to a specific page, say page 18.

Click the circle numbered 18 below.

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

What did it do? It visited all 18 pages before reaching the desired page. This is how linear search works.

Now again click the circle numbered 18 below.

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

What did it do? It visited only 4 pages before reaching the desired page. This is how binary search works.

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 is exhausted.

Pseudocode

Using this pseudocode, we can implement binary search in any programming language. Try to implement it in your favorite language and see if it works.

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

We can implement binary search in two ways. One is iterative and the other is recursive. Let's implement both of them.

Binary search only works on sorted lists. If the list is not sorted, the algorithm will not work.

Binary Search using Iteration

Here is the iterative implementation of binary search in C, Java, Python, PHP, and JavaScript.

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

Here is the recursive implementation of binary search in C, Java, Python, PHP, and JavaScript.

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);
    }
}

Time Complexity

The time complexity of binary search is O(log n). This is because the search space is reduced by half at every iteration.

At innitial iteration, the search space is n. At the next iteration, the search space is reduced to n/2. At the next iteration, the search space is reduced to n/4. This continues until the search space is reduced to 1.

The number of iterations required to reduce the search space to 1 is given by log n. Therefore, the time complexity of binary search is O(log n).

Space Complexity

Binary search is an in-place algorithm. Therefore, the worst-case space complexity of binary search is O(1).

In-place algorithm means that the algorithm does not require any extra space to perform the computation. The input array is used as the auxiliary space.
CaseTime ComplexitySpace Complexity
BestO(1)O(1)
AverageO(log n)O(1)
WorstO(log n)O(1)

Binary search is much faster than linear search. Let's see how much faster it is.

Let's say have a sorted list of numbers 1 to 7 and we want to find the number 5 in it.

Using Binary Search Algorithm

So we start from the middle of the list which is 4. As 4 is not the number we are looking for we check if the number we are looking for is before or after 4.

5 is after 4 so we will eliminate the first half of the list and search in the second half.

Again we will start from the middle of the list which is 6. As 6 is not the number we are looking for we check if the number we are looking for is before or after 6.

5 is before 6 so we will eliminate the second half of the list and search in the first half.

Again we will start from the middle of the list which is 5. As 5 is the number we are looking for we will return the index of 5 which is 4.

To find the number 5 in the list we had to check 3 times.

Using Linear Search Algorithm

In the case of linear search, we will start from the first element of the list which is 1. As 1 is not the number we are looking for we will check the next element which is 2. 2 is not the desired number so we will keep checking the next element until we find the number 5.

To find the number 5 we will have to check 5 times.

If the list had 100 elements then in the case of linear search we would have to check 100 elements to find the desired number.

But in the case of binary search, we would have to check only 7 elements. So we can see that binary search is much faster than linear search.

Binary search is used to search data in a sorted list. It is used in many applications such as searching for a word in a dictionary, searching for a name in a phone book, searching for a number in a sorted list, etc.

  • Binary search is one of the fastest search algorithm.
  • Binary search is an in-place algorithm and it doesn't require any extra space.
  • Binary search is easy to implement.
  • Binary search can only be used to search data in a sorted list.
  • Binary search is not suitable for searching data in a linked list.

Common Questions

Question: What is the time complexity of binary search?

Answer: The time complexity of binary search is O(log n).

Question: What is the space complexity of binary search?

Answer: The space complexity of binary search is O(1).

Question: What is a divide and conquer algorithm?

Answer: Divide and conquer algorithm is an algorithm that divides the problem into smaller sub-problems and solves them recursively. Then it combines the results of the sub-problems to solve the original problem.

Question: What is the difference between linear search and binary search?

Answer: Linear search is a searching algorithm that searches the list sequentially. Binary search is a searching algorithm that divides the list into two halves and searches the list recursively.

Conclusion

In this article, we learned about binary search and how it works, its complexity, and its applications. We also learned how to implement binary search in both recursive and iterative ways in different programming languages.

Hope this article was helpful. If you have any questions or suggestions, please leave a comment below.

References