C Program to Implement Binary Search

Introduction

Binary search is a highly efficient searching algorithm that works on sorted arrays. It repeatedly divides the array into halves, reducing the search space by half each time, until it finds the target element or determines that the element is not present. This guide will show you how to write a C program to implement binary search.

Problem Statement

Create a C program that:

• Takes the size of the array as input from the user.
• Takes the elements of the array as input (the array must be sorted).
• Takes the key element to search for in the array.
• Performs a binary search to find the key element.
• Displays the index of the key element if found, or a message indicating that the element is not found.

Example:

• Input: Array size = 6, Elements = [3, 9, 18, 27, 34, 42], Key = 27
• Output: Element found at index 3

Solution Steps

1. Include the Standard Input-Output Library: Use #include <stdio.h> to include the standard input-output library, which is necessary for using printf and scanf functions.
2. Write the Main Function: Define the main function, which is the entry point of every C program.
3. Declare Variables: Declare variables to store the array size, the array elements, the key element, and indices for the search.
4. Input the Array Size: Use scanf to take input from the user for the size of the array.
5. Input the Array Elements: Use a loop to take input from the user for the elements of the array.
6. Input the Key Element: Use scanf to take input from the user for the key element to search for.
7. Perform Binary Search: Implement the binary search algorithm to find the key element in the sorted array.
8. Display the Result: If the key is found, display its index; otherwise, display a message indicating that the element is not found.

C Program

#include <stdio.h>

/**
 * C Program to Implement Binary Search
 * Author: https://www.javaguides.net/
 */
int main() {
    // Step 1: Declare variables to hold the array size, elements, key, and indices
    int n, key, low, high, mid;

    // Step 2: Prompt the user to enter the size of the array
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    // Step 3: Declare an array to hold the elements
    int arr[n];

    // Step 4: Input the array elements (ensure they are sorted)
    printf("Enter %d sorted elements:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Step 5: Prompt the user to enter the key element to search for
    printf("Enter the element to search: ");
    scanf("%d", &key);

    // Step 6: Initialize the indices for binary search
    low = 0;
    high = n - 1;

    // Step 7: Perform binary search
    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == key) {
            printf("Element found at index %d\n", mid);
            return 0;
        } else if (arr[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    // Step 8: If the loop completes, the element was not found
    printf("Element not found in the array\n");

    return 0;  // Step 9: Return 0 to indicate successful execution
}

Explanation

Step 1: Declare Variables

• The variable n is declared to store the size of the array. key stores the element to be searched. low, high, and mid are used as indices for the binary search.

Step 2: Input the Array Size

• The program prompts the user to enter the size of the array using printf. The scanf function then reads the input and stores it in the variable n.

Step 3: Declare the Array

• The program declares an array arr of size n to hold the elements provided by the user.

Step 4: Input the Array Elements

• The program uses a for loop to take input for each element of the array. The elements must be entered in sorted order for binary search to work correctly.

Step 5: Input the Key Element

• The program prompts the user to enter the key element they wish to search for in the array.

Step 6: Initialize Indices for Binary Search

• The program initializes low to 0 (the start of the array) and high to n-1 (the end of the array).

Step 7: Perform Binary Search

• The program enters a while loop that continues as long as low is less than or equal to high:
  • Step 7.1: Calculate the middle index mid as (low + high) / 2.
  • Step 7.2: Compare the middle element arr[mid] with the key:
    • If arr[mid] equals key, the element is found, and its index is displayed.
    • If arr[mid] is less than key, the search continues in the right half by updating low to mid + 1.
    • If arr[mid] is greater than key, the search continues in the left half by updating high to mid - 1.

Step 8: Display the Result

• If the loop completes without finding the key, the program displays a message indicating that the element was not found in the array.

Step 9: Return 0

• The return 0; statement indicates that the program executed successfully.

Output Example

Example:

Enter the number of elements in the array: 6
Enter 6 sorted elements:
3
9
18
27
34
42
Enter the element to search: 27
Element found at index 3

Example (Element Not Found):

Enter the number of elements in the array: 5
Enter 5 sorted elements:
10
20
30
40
50
Enter the element to search: 25
Element not found in the array

Conclusion

This C program demonstrates how to implement a binary search algorithm. It covers essential concepts such as arrays, loops, and conditional statements, making it a valuable example for beginners learning C programming and understanding efficient searching techniques.