Binary Search

Binary Search

Binary search is a highly efficient searching algorithm used to find a target value within a sorted array or list. It operates by repeatedly dividing the search interval in half until the target value is found or the interval is empty.

Here’s how the binary search algorithm works:

1. Initialize pointers: Set two pointers, left and right, to the first and last elements of the array, respectively.
2. Midpoint calculation: Calculate the midpoint of the array as (left + right) / 2.
3. Compare with the midpoint: Compare the target value with the value at the midpoint.
4. Adjust pointers: If the target value matches the midpoint value, the search is complete. If the target value is less than the midpoint value, set right = mid - 1 to search the left half of the array. If the target value is greater than the midpoint value, set left = mid + 1 to search the right half of the array.
5. Repeat: Repeat steps 2-4 until the target value is found or until left is greater than right.

Binary search is a divide-and-conquer algorithm that halves the search space at each step. As a result, it has a time complexity of O(logn), where n is the number of elements in the array or list.

Here’s a simple implementation of binary search in C:

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // Check if target is present at mid
        if (arr[mid] == target)
            return mid;
        // If target greater, ignore left half
        if (arr[mid] < target)
            left = mid + 1;
        // If target is smaller, ignore right half
        else
            right = mid - 1;
    }
    // If target is not present in array
    return -1;
}

int main() {
    int arr[] = {2, 3, 5, 9, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 9;

    int index = binarySearch(arr, 0, n - 1, target);

    if (index != -1) {
        printf("Element %d found at index %d\n", target, index);
    } else {
        printf("Element %d not found in the array\n", target);
    }

    return 0;
}

Output:

Element 9 found at index 3

Code Explanation

1. binarySearch Function

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // Check if target is present at mid
        if (arr[mid] == target)
            return mid;
        // If target greater, ignore left half
        if (arr[mid] < target)
            left = mid + 1;
        // If target is smaller, ignore right half
        else
            right = mid - 1;
    }
    // If target is not present in array
    return -1;
}

• Purpose: This function performs a binary search on a sorted array to find the index of a target element.
• Parameters:
  • int arr[]: The sorted array in which the search is performed.
  • int left: The starting index of the search range.
  • int right: The ending index of the search range.
  • int target: The element to be searched in the array.
• Logic:
  1. The function uses a while loop to repeatedly divide the search range in half.
  2. It calculates the middle index (mid) of the current search range.
  3. If the middle element (arr[mid]) matches the target, it returns the index mid.
  4. If the middle element is less than the target, the search continues in the right half of the array (left = mid + 1).
  5. If the middle element is greater than the target, the search continues in the left half of the array (right = mid - 1).
  6. If the loop ends without finding the target, the function returns -1 to indicate that the target is not present in the array.

2. main Function

int main() {
    int arr[] = {2, 3, 5, 9, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 9;
 
    int index = binarySearch(arr, 0, n - 1, target);
 
    if (index != -1) {
        printf("Element %d found at index %d\n", target, index);
    } else {
        printf("Element %d not found in the array\n", target);
    }
 
    return 0;
}

• Purpose: The main function initializes a sorted array, calls the binarySearch function, and prints the result.
• Steps:
  1. Array Initialization:

int arr[] = {2, 3, 5, 9, 13};

A sorted array arr is initialized with 5 integers: {2, 3, 5, 9, 13}.

2. Calculate Array Size:

int n = sizeof(arr) / sizeof(arr[0]);

• sizeof(arr) gives the total size of the array in bytes.
• sizeof(arr[0]) gives the size of one element in the array.
• Dividing the total size by the size of one element gives the number of elements in the array (n = 5 in this case).

3. Target Initialization:

int target = 9;

The target element to be searched is set to 9.

4. Call binarySearch Function:

int index = binarySearch(arr, 0, n - 1, target);

• The binarySearch function is called with the array arr, the starting index 0, the ending index n - 1, and the target 9.
• The function returns the index of the target if found, or -1 if not found.

5. Check and Print Result:

if (index != -1) {
    printf("Element %d found at index %d\n", target, index);
} else {
    printf("Element %d not found in the array\n", target);
}
return 0;
}

• If the index is not -1, it means the target was found, and the program prints the index.
• If the index is -1, it means the target was not found, and the program prints a “not found” message.
• The main function returns 0, indicating successful execution.

Key Points of Binary Search

1. Requirement: The array must be sorted.
2. Time Complexity: O(log n) — much faster than linear search (O(n)) for large datasets.
3. Space Complexity: O(1) — it uses a constant amount of extra space.
4. Efficiency: Ideal for large datasets where the array is already sorted.