Skip to main content
1 of 8
Aseem Bansal
  • 2.3k
  • 3
  • 22
  • 37

Binary Search in C - Optimization

I know that there is a function bsearch present in stdlib.h but still I want to implement this.

This is my code for binary search. Any and all reviews are welcome.

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

int compare (const void * a, const void * b)
{
    return (*(int*)a - *(int*)b);
}

int bin_search(int arr[], int min_index, int max_index, int element)
{
    /*
    Searches for an element in the array arr
    Returns fist index of element if present else returns -1
    */
    if (min_index > max_index){
        return -1;
    }
    else
    {
        //Don't change this assignment of mid_point. It avoids overflow
        int mid_point = min_index + (max_index - min_index)/2;

        if (arr[mid_point] > element){
            return bin_search(arr, min_index, mid_point, element);
        }
        else if (arr[mid_point] < element){
            return bin_search(arr, mid_point, max_index, element);
        }
        else{
            return mid_point;
        }
    }
}

int main()
{
    int length;
    while (1)
    {
        printf("Enter a positive length: ");
        scanf("%d", &length);
        if (length > 1){
            break;
        }
        else{
            printf("You entered length = %d\n\n", length);
        }
    }

    int *arr = malloc(sizeof(int) * length);
    if (arr == NULL)
    {
        perror("The following error occurred");
        exit(-1);
    }

    for (int i = 0; i < length; i++){
        scanf("%d", &arr[i]);
    }

    int element;
    printf("\nEnter the element to be searched: ");
    scanf("%d", &element);

    qsort(arr, length, sizeof(int), compare);
    int index = bin_search(arr, 0, length - 1, element);

    if (index == -1){
        printf("\nElement not in the array");
    }
    else{
        printf("\nIndex of element is %d", index);
    }

    free(arr);
    return 0;
}
Aseem Bansal
  • 2.3k
  • 3
  • 22
  • 37