Binary Search

Introduction

Binary search is an efficient algorithm for finding a specific value in a sorted array. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the search continues in the lower half; otherwise, it continues in the upper half. This method drastically reduces the number of comparisons needed to find the target value, making it much faster than linear search for large datasets.

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        // Check if the target is present at mid
        if (arr[mid] == target) {
            return mid; // Return the index if found
        }
        // If target is greater, ignore the left half
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        // If target is smaller, ignore the right half
        else {
            right = mid - 1;
        }
    }
    return -1; // Return -1 if not found
}

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

    printf("Enter the number to search: ");
    scanf("%d", &target);

    int result = binarySearch(arr, size, target);

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

    return 0;
}

Explanation

1. Function Definition:
   • binarySearch(int arr[], int size, int target): Takes a sorted array, its size, and the target value to search for.
2. Initialization:
   • Two pointers, left and right, are initialized to the start and end of the array, respectively.
3. Loop:
   • A while loop runs as long as left is less than or equal to right.
   • The middle index (mid) is calculated, and the target is compared with the value at mid.
   • Depending on the comparison:
     • If the target equals arr[mid], the index is returned.
     • If the target is greater, left is updated to mid + 1.
     • If the target is smaller, right is updated to mid - 1.
4. Return Values:
   • Returns the index of the target if found.
   • Returns -1 if the target is not found.
5. Main Function:
   • Initializes a sorted array and prompts user input for the target value.
   • Calls binarySearch and displays the result.

Input

When you run the program, it prompts the user to enter a number to search for. For example:

Enter the number to search: 7

Output

The output will indicate whether the element was found and, if so, at which index:

Element found at index: 3

Or if the element is not found:

Element not found in the array.

Conclusion

Binary search is a highly efficient algorithm for searching elements in a sorted array, with a time complexity of O(log n). This makes it significantly faster than linear search, especially for larger datasets. However, it is crucial that the array is sorted before applying binary search. Its effectiveness and efficiency make it a popular choice in many applications where fast search operations are required.