Program for binary search |Data Structure in C|

Introduction

     Searching for an element in an array is a common operation in computer science. Binary Search is a highly efficient algorithm for finding an element in a sorted array. This C program demonstrates the implementation of Binary Search, providing insights into how it works and its advantages over linear search.  

Code

    
     
    #include<stdio.h>
    #include<conio.h>

    void main() {
        int a[20], start, end, mid, n, i, item;
        clrscr();

        // Input
        printf("How many elements: ");
        scanf("%d", &n);
        printf("Enter the elements (in sorted order): ");
        for (i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }

        // Searching
        printf("Enter the element to be searched: ");
        scanf("%d", &item);
        start = 0;
        end = n - 1;
        mid = (start + end) / 2;

        while (item != a[mid] && start <= end) {
            if (item > a[mid])
                start = mid + 1;
            else
                end = mid - 1;
            mid = (start + end) / 2;
        }

        // Output
        if (item == a[mid])
            printf("%d found at position %d", item, mid + 1);
        if (start > end)
            printf("Item not found in the array");

        getch();
    }
   
       
     

Output

    How many elements: 7
    Enter the elements (in sorted order): 10 20 30 40 50 60 70
    Enter the element to be searched: 40
    
    40 found at position 4
       

    In this example, the user inputs seven sorted elements (10, 20, 30, 40, 50, 60, 70) into the array. The program then searches for the element 40 using Binary Search and successfully finds it at position 4.

You can try running the program with different sets of sorted elements and search for various items to observe how Binary Search efficiently locates elements in a sorted array. The output will indicate the position of the found element or inform you if the item is not present in the array.

Explanation

1.  Header Files:

The program includes the standard input/output header <stdio.h> and the console input/output header <conio.h>.

2. Main Function:

The main function serves as the entry point of the program.

3. Input:

Users input the number of elements and the sorted array.

4. Binary Search Algorithm:

The program employs the Binary Search algorithm to find the specified element in the sorted array.

The search range (start to end) is adjusted based on comparisons with the middle element (mid).

5. Output:

The program outputs the position of the found element or a message indicating that the item was not found.

Advantages of Binary Search

1. Efficiency: 

Binary Search has a time complexity of O(log n), making it highly efficient, especially for large datasets.

2. Sorted Data Requirement: 

Binary Search requires the data to be sorted, but it provides significant advantages in terms of search time.

Conclusion

     This C program provides a practical example of implementing Binary Search, an algorithm known for its efficiency in searching sorted arrays. Understanding and applying Binary Search is crucial for optimizing search operations in various applications. Feel free to run the program with different sets of sorted elements to observe how Binary Search efficiently locates the specified element. This example serves