Binary Search Algorithm

Last updated on July 13th, 2024 at 10:24 am

We will discuss the Binary Search Algorithm, pseudo code, Code implementation of Binary Search Algorithm in C, C++, Java, JavaScript, Python, advantages & disadvantages, and time & space complexity of Binary Search Algorithm.

1. What is Binary Search?

Binary Search is the most popular search algorithm. It is efficient and most commonly used to solve problems.

Binary Search relies on a divide-and-conquer strategy to find an element within a sorted list.

Binary Search compares the element to be searched with the middle element of an array. If the element is equal to the middle element, the search stops here and the position of an element is returned. If it is less or greater than the middle element, then the values of the sub-array are adjusted accordingly. The algorithm returns a unique value: the element’s position in the list if the element is present.

Binary search works only on a sorted array. To use binary search, the array must be sorted first.

1.1 Pseudocode for Binary Search

BINARY_SEARCH (A, value, left, right) 
1. if right < left 
2. return ‘not found’ 
3. mid = floor((right-left)/2)+left 
4. if A[mid] = value 
5. return mid 
6. if value < A[mid] 
7. return BINARY_SEARCH(A, value, left, mid-1) 
8. else 
9. return BINARY_SEARCH(A, value, mid+1, right)

2. Implementation of Binary Search Algorithm

2.1 Binary Search Algorithm in C

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return mid;
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

int main() {
    int arr[] = {3, 15, 8, 1, 38, -2, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 8;
    int result = binarySearch(arr, 0, n - 1, target);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");
    return 0;
}

2.1.1 Code Explanation of Binary Search

1. binarySearch function takes an array arr[], the lower bound low, the upper bound high, and the element to be searched x.
2. It performs binary search iteratively using a while loop.
3. It calculates the middle index mid as (low + high) / 2.
4. If the middle element is equal to x, it returns the index.
5. If the middle element is less than x, it updates the lower bound to mid + 1.
6. If the middle element is greater than x, it updates the upper bound to mid-1.
7. The loop continues until the element is found or until the low is greater than the high.
8. In the main function, an array arr[] is defined along with its size n and the element to be searched x.
9. The binarySearch function is called with appropriate arguments, and the result is printed.

2.2 Binary Search Algorithm in C++

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& arr, int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return mid;
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

int main() {
    vector<int> arr = {3, 15, 8, 1, 38, -2, 7};
    int n = arr.size();
    int target = 8;
    int result = binarySearch(arr, 0, n - 1, target);
    if (result != -1)
        cout << "Element found at index " << result << endl;
    else
        cout << "Element not found" << endl;
    return 0;
}

2.3 Binary Search Algorithm in Java

public class BinarySearch {
    public static int binarySearch(int[] arr, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target)
                return mid;
            if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {3, 15, 8, 1, 38, -2, 7};
        int target = 8;
        int result = binarySearch(arr, 0, arr.length - 1, target);
        if (result != -1)
            System.out.println("Element found at index " + result);
        else
            System.out.println("Element not found");
    }
}

2.4 Binary Search Algorithm in JavaScript

function binarySearch(arr, left, right, target) {
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (arr[mid] === target)
            return mid;
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

let arr = [3, 15, 8, 1, 38, -2, 7];
let target = 8;
let result = binarySearch(arr, 0, arr.length - 1, target);
if (result !== -1)
    console.log("Element found at index " + result);
else
    console.log("Element not found");

2.5 Binary Search Algorithm in Python

def binary_search(arr, left, right, target):
    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

arr = [3, 15, 8, 1, 38, -2, 7]
target = 8
result = binary_search(arr, 0, len(arr) - 1, target)
if result != -1:
    print("Element found at index", result)
else:
    print("Element not found")

3. Time Complexity of Binary Search

Time Complexity
Worst Case	O(log n)
Best Case	O(1)
Average Case	O(log n)
Space Complexity
Worst Case	O(n)

4. Advantages of Binary Search

• Efficient for searching in sorted arrays.
• Time complexity is O(log n), which means it’s highly efficient for large datasets.

5. Disadvantages of Binary Search

• Requires the array to be sorted beforehand.
• If the array is not sorted, a sorting operation needs to be performed first, which could be an additional overhead.
• Binary search is not suitable for linked lists or data structures where direct access to elements is not efficient.

FAQs