Table of contents

Binary Search Algorithm

Binary Search is a highly efficient searching algorithm used to find the position of a target element in a sorted array or list. It works by repeatedly dividing the search interval in half, which reduces the problem size logarithmically. The algorithm compares the target value to the middle element of the array and eliminates half of the remaining elements with each comparison.

Binary Search significantly improves the search time over a linear search and is optimal for large sorted datasets.

How Binary Search Works

Binary Search works by leveraging the sorted nature of the array to eliminate half of the elements in each iteration. The algorithm checks the middle element of the array and determines if the target value is smaller or larger than the middle element:

  • If the target is equal to the middle element, the search is successful.
  • If the target is smaller than the middle element, the search continues on the left half.
  • If the target is larger than the middle element, the search continues on the right half.

Step-by-step explanation:

  1. Start with the whole array: Initialize two pointers, low (starting at the first element) and high (starting at the last element).
  2. Calculate the middle element: Find the middle element by calculating (low + high) // 2.
  3. Compare the target with the middle element:
    • If the target equals the middle element, return the index of the middle element.
    • If the target is smaller than the middle element, repeat the process for the left half of the array.
    • If the target is larger than the middle element, repeat the process for the right half of the array.
  4. Repeat this process until the target is found or the search interval becomes empty (low > high).

Let’s take an example of searching for the value 40 in the sorted array [10, 20, 30, 40, 50, 60]:

  1. Initial List: [10, 20, 30, 40, 50, 60]
  2. Target Element: 40
  3. Start with the entire array: low = 0, high = 5
  4. Step 1: Middle element is at index (0 + 5) // 2 = 2, value is 30.
    • Compare 30 with 40 → Target is larger, so search the right half.
    • New low = 3, high = 5
  5. Step 2: Middle element is at index (3 + 5) // 2 = 4, value is 50.
    • Compare 50 with 40 → Target is smaller, so search the left half.
    • New low = 3, high = 3
  6. Step 3: Middle element is at index (3 + 3) // 2 = 3, value is 40.
    • Target found at index 3.

C++ Program to implement Binary Search Algorithm

cpp
#include <iostream>
using namespace std;

// Function to perform binary search
int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;  // Calculate the middle element

        // Check if the target is the middle element
        if (arr[mid] == target) {
            return mid;  // Target found, return the index
        }

        // If target is greater, ignore the left half
        if (arr[mid] < target) {
            low = mid + 1;
        }
        // If target is smaller, ignore the right half
        else {
            high = mid - 1;
        }
    }
    return -1;  // Target not found
}

// Main function
int main() {
    int arr[] = {10, 20, 30, 40, 50, 60};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 40;

    int result = binarySearch(arr, n, target);
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found in the array." << endl;
    }

    return 0;
}

Java Program to implement Binary Search Algorithm

java
public class Main {
    // Function to perform binary search
    public static int binarySearch(int arr[], int target) {
        int low = 0, high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;  // Calculate the middle element

            // Check if the target is the middle element
            if (arr[mid] == target) {
                return mid;  // Target found, return the index
            }

            // If target is greater, ignore the left half
            if (arr[mid] < target) {
                low = mid + 1;
            }
            // If target is smaller, ignore the right half
            else {
                high = mid - 1;
            }
        }
        return -1;  // Target not found
    }

    // Main function
    public static void main(String[] args) {
        int arr[] = {10, 20, 30, 40, 50, 60};
        int target = 40;

        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

Python Program to implement Binary Search Algorithm

python
# Function to perform binary search
def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2  # Calculate the middle element

        # Check if the target is the middle element
        if arr[mid] == target:
            return mid  # Target found, return the index

        # If target is greater, ignore the left half
        elif arr[mid] < target:
            low = mid + 1
        # If target is smaller, ignore the right half
        else:
            high = mid - 1

    return -1  # Target not found

# Main function
if __name__ == "__main__":
    arr = [10, 20, 30, 40, 50, 60]
    target = 40

    result = binary_search(arr, target)
    if result != -1:
        print(f"Element found at index: {result}")
    else:
        print("Element not found in the array.")
  • Time Complexity:
    • Best Case: O(1) - when the middle element is the target.
    • Average Case: O(log n) - because the problem size is halved with each iteration.
    • Worst Case: O(log n) - when the target is not found or at the end of the array.
  • Space Complexity: O(1) - for iterative Binary Search. If implemented recursively, the space complexity is O(log n) due to the recursive call stack.
  • Stability: Binary Search is not typically associated with stability, as it only searches for a single element without modifying the array.
  • Adaptability: Binary Search requires a sorted array and is not suitable for unsorted datasets.

Binary Search is highly efficient for searching in large, sorted datasets. It is much faster than Linear Search for large arrays because it reduces the search space logarithmically. However, Binary Search can only be used on arrays that are already sorted. For unsorted arrays, sorting the array first (O(n log n)) may negate the benefits of Binary Search.

DSA

Related Articles