Skip to main content
6 of 8
changed a comparison
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 - 1, element);
        }
        else if (arr[mid_point] < element){
            return bin_search(arr, mid_point + 1, 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;
}

Thanks to @Josay for pointing out an infinite loop that I didn't know about in the original code.


Updated Code after answer by William Morris

static int bin_search(const int arr[], int min, int max, const int element)
{
    /*
    Searches for an element in the array arr
    Returns index of element if present else returns -1
    */
    if (min > max){
        return -1;
    }

    //Don't change this assignment of mid. It avoids overflow
    int mid = min + (max - min)/2;

    if (arr[mid] > element){
        return bin_search(arr, min + 1, mid, element);
    }
    else if (arr[mid] < element){
        return bin_search(arr, mid, max - 1, element);
    }
    return mid;
}

After Ruds answer and some thinking I came up with a solution that uses the same number of comparison as his answer but doesn't have the flaw, of accessing uninitialized memory in case the user isn't careful, which he had pointed out.

I broke up the bin_search function into 2 parts. The main bin_search takes care of uninitialized memory and then tail-recursive procedure bin_proc is started. It adds 1 comparison for any search(not for each recursive call). The complexity becomes the same as suggested in Ruds' answer without that flaw.

static int bin_proc(const int arr[], int min, int max, int element)
{
    if (min >= max){
        return arr[max] == element ? max : -1;
    }

    //Don't change this assignment of mid. It avoids overflow
    int mid = min + (max - min)/2;
    if (arr[mid] > element) {
        return bin_proc(arr, min, mid, element);
    }
    else {
        return bin_proc(arr, mid + 1, max, element);
    }
}

int bin_search(const int arr[], int length, int element)
{
    /*
    Searches for an element in the array arr
    If present returns index else returns -1
    */
    if (length < 1){
        return -1;
    }
    return bin_proc(arr, 0, length - 1, element);
}
Aseem Bansal
  • 2.3k
  • 3
  • 22
  • 37