Index « Previous Next »

Question

Write a program to searh an integer array for a given item using binary search algorithm.

Binary search algorithm finds an item from a sorted list of items. Binary search compares the item to the middle element of the array. If they are not equal, the half in which the item cannot lie is eliminated and the search continues on the remaining half.

Again, taking the middle element to compare to the item, and repeating this until the target value is found. If the search ends with the remaining half being empty, the item is not in the array.

Source Code

#include <stdio.h>

int bSearchAsc(int A[], int s, int data);

int main()
{
    int list[100], n, val, i;
    int found;

    printf("Enter the number of elements you want to insert : ");
    scanf("%d", &n);

    printf("Enter element in ascending order \n");

    for (i = 0; i < n; i++)
    {
        printf("Enter element %d : ", i + 1);
        scanf("%d", &list[i]);
    }

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

    found = bSearchAsc(list, n, val);

    if (found ==  - 1)
    {
        printf("\nItem not found");
    }
    else
    {
        printf("\nItem found at %d", found);
    }

    return 0;
}

int bSearchAsc(int A[], int s, int data)
{
    int mid, first = 0, last = s - 1;
    
    while (first <= last)
    {
        mid = (first + last) / 2;
        if (data > A[mid])
        {
            first = mid + 1;
        }
        else if (data < A[mid])
        {

            last = mid - 1;
        }
        else
        {
            return mid + 1;
        }
    }

    return  - 1;
}

Output

Enter the number of elements you want to insert : 5
Enter element in ascending order
Enter element 1 : 12
Enter element 2 : 18
Enter element 3 : 23
Enter element 4 : 27
Enter element 5 : 30
Enter the number you want to search : 27

Item found at 4