Binary Search using C

This example shows how Binary Search Algorithm works and I am going to implement it using C programming language. Binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.

Binary search algorithm is better when an array is sorted because it makes comparison between the search key “k” and middle element of the array. Since the array is sorted, the comparison results either in a match between “k” and the middle element of the array or identifying the left half or right half of the array to which the desired element may belong. This process continues on the half in which the desired element may be present in case “k” is not equal to the middle element. In this way, either the element is detected or the final division leads to a half, where the array does not contain the desired element “k”.

This is very efficient method of searching algorithm because the comparison enables one to eliminate half of the elements from further consideration.

Time & Space Complexity

Time complexity of binary search algorithm is given below in different cases:

Worst complexity: O(log n)
Average complexity: O(log n)
Best complexity: O(1)
Space complexity: O(1)

Binary Search Implementation

The complete source code of binary search algorithm using C programming language is given below:

/* 
 * File:   BinarySearch.c
 * Author: https://roytuts.com
 */

#include <stdio.h>
#include <stdlib.h>

int binarySearch(int k, int a[], int n) {
    int i = -1;
    int lower = 0, mid;
    int upper;
    upper = n - 1;
    while (upper >= lower) {
        mid = (upper + lower) / 2;
        if (k == a[mid]) {
            i = mid;
            break;
        } else {
            if (k > a[mid]) {
                lower = mid + 1;
            } else {
                upper = mid - 1;
            }
        }
    }
    return i;
}

int main() {
    int choice, value;
    int a[] = {10, 25, 48, 69, 94, 105, 116};
    printf("\n:: Binary Search ::\n");
    while (1) {
        printf("\nChoose from below Menu\n");
        printf("1. Search\n2. Exit\n");
        printf("\nEnter your choice: ");
        scanf("%d", &choice);
        switch (choice) {
            case 1: printf("Enter the value to be searched: ");
                scanf("%d", &value);
                int index = binarySearch(value, a, 7);
                if (index >= 0) {
                    printf("\nValue found at index %d in the array\n", index);
                } else {
                    printf("\nValue not found in the array\n");
                }
                break;
            case 2: exit(0);
            default: printf("\nWrong selection!!! Please try again!!!\n");
        }
    }
}

Testing the Program

Executing the above program will give you the following output:

:: Binary Search ::

Choose from below Menu
1. Search
2. Exit

Enter your choice: 1
Enter the value to be searched: 10

Value found at index 0 in the array

Choose from below Menu
1. Search
2. Exit

Enter your choice: 1
Enter the value to be searched: 105

Value found at index 5 in the array

Choose from below Menu
1. Search
2. Exit

Enter your choice: 2

Source Code

Download

Leave a Reply

Your email address will not be published. Required fields are marked *