Binary Search for Sorted Arrays

Binary Search for Sorted Arrays

Binary search is a highly efficient algorithm for finding an element's position in a sorted array. Unlike linear search, which checks each element sequentially, binary search works by repeatedly dividing the search interval in half. This requires the array to be sorted beforehand.

Key Characteristics

1. Precondition: The array must be sorted in ascending (or descending) order.
2. Time Complexity: The worst-case time complexity is $O(\log n)$, where $n$ is the number of elements in the array.
3. Space Complexity: The space complexity is $O(1)$ for the iterative version and $O(\log n)$ for the recursive version due to call stack usage.

How Binary Search Works

1. Initialization: Start with two pointers, low and high, which represent the bounds of the search area. Initially, low is set to the first index (0), and high is set to the last index (n - 1).
2. Calculate Midpoint: Compute the midpoint index: mid = (low + high) / 2.
3. Comparison:
   • If the target value equals the element at the midpoint, the search is successful.
   • If the target value is less than the element at the midpoint, narrow the search to the left half by updating high.
   • If the target value is greater than the element at the midpoint, narrow the search to the right half by updating low.
4. Repeat: Continue the process until the target is found or the search interval is empty (low > high).

Example Code

Here’s a simple C++ implementation of binary search for a sorted array:

#include <iostream>
using namespace std;

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

    while (low <= high) {
        int mid = low + (high - low) / 2; // Avoids potential overflow

        if (arr[mid] == target) {
            return mid; // Return the index if found
        } else if (arr[mid] < target) {
            low = mid + 1; // Search in the right half
        } else {
            high = mid - 1; // Search in the left half
        }
    }
    return -1; // Return -1 if the target is not found
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11}; // Example sorted array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

    int result = binarySearch(arr, size, target);
    if (result != -1) {
        cout << "Element found at index: " << result << endl; // Output: Element found at index: 3
    } else {
        cout << "Element not found." << endl; // Output if not found
    }

    return 0;
}

Explanation of the Code

1. Function Definition: The binarySearch function takes a sorted array, its size, and the target value as parameters.
2. Initialization: low is set to 0 and high to the last index of the array.
3. Loop: The while loop continues as long as low is less than or equal to high.
4. Midpoint Calculation: The midpoint index is calculated. Using low + (high - low) / 2 helps avoid potential overflow.
5. Comparison:
   • If the target is found at mid, its index is returned.
   • If the target is less than the midpoint value, the search continues in the left half by updating high.
   • If the target is greater, the search continues in the right half by updating low.
6. Return Value: If the target is not found, the function returns -1.
7. Main Function: Initializes a sorted array, specifies a target value, calls binarySearch, and prints the result.

Complexity Analysis

• Time Complexity:
  • The algorithm operates in $O(\log n)$ time, making it very efficient for large datasets.
• Space Complexity:
  • The iterative version uses $O(1)$ space. The recursive version uses $O(\log n)$ space due to recursion stack.

Conclusion

Binary search is a powerful and efficient algorithm for searching in sorted arrays. Its logarithmic time complexity allows it to handle large datasets efficiently, making it a fundamental technique in computer science and programming. Always ensure that the array is sorted before applying binary search, as it relies on the order of elements for its functionality.