C Program to Search an Element in an Array Using Binary Search

1. Introduction

Binary search is a divide-and-conquer algorithm used for searching a particular value in a sorted list. It compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half until it is successful or the remaining half is empty.

2. Program Overview

In this program, we will:

1. Declare a sorted array and initialize it with some values.

2. Take an input number from the user that we want to search in the array.

3. Use binary search to find the number in the array.

4. Print the result: either the index of the number (if found) or a message indicating it wasn't found.

3. Code Program

#include <stdio.h>

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int mid = l + (r - l) / 2;

        // Check if x is present at mid
        if (arr[mid] == x)
            return mid;

        // If x is greater, ignore left half
        if (arr[mid] < x)
            l = mid + 1;

        // If x is smaller, ignore right half
        else
            r = mid - 1;
    }

    // If we reach here, then the element was not present
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x;

    // Ask user for the number to be searched
    printf("Enter the number to search: ");
    scanf("%d", &x);

    // Binary search process
    int result = binarySearch(arr, 0, n-1, x);

    // Display the result
    (result == -1) ? printf("Number %d is not present in the array.\n", x)
                   : printf("Number %d is present at index %d.\n", x, result);
    return 0;
}

Output:

For input 7:
Number 7 is present at index 3

For input 2:
Number 2 is not present in the array.

4. Step By Step Explanation

1. We start by declaring and initializing a sorted array arr with 10 integer values.

2. We also have a function binarySearch which takes in the array, left and right indices, and the number to be searched. This function implements the core logic of the binary search.

3. The main function prompts the user to input the number they wish to search for.

4. Using the binarySearch function, the main function looks for the input number in the array.

5. The result is then checked and printed. If the binarySearch function returns -1, it means the number is not present in the array. Otherwise, the returned value is the index of the number.