Thoughts on BinSearch algorithm?

[creeps]

I've written the following binary search algorithm and it worked on my tests. I want to know if there is something I'm missing, as this is the first time I try to write it, so give me a case in which it would fail, and I'll try fixing it.

I know I don't have a sorting algorithm implemented (I will, shortly) and I know it doesn't work if the numbers are too big.

#include<stdio.h>

int bsearch(int a[], int length, int n);

int main(void) {

    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, n, result;

    printf("Enter a number: ");
    scanf("%d", &n);

    result = bsearch(a, 1, n);

    if(result < 0) {

        printf("Element not in array");
    } else {

        printf("Element found: %d", a[result]);
    }

    printf("\n");

    return 0;
}

int bsearch(int a[], int length, int n) {

    int min = 0, max = length, mid = max / 2;

    if(length < 2) {

        if(a[0] == n) {

            return 0;
        }
    } else {

        return 1;
    }

    while(min != mid) {

        if(n < a[mid]) {
        
            max = mid;
            mid = (max + min) / 2;
        } else if(n > a[mid]) {

            min = mid;
            mid = (min + max) / 2;
        } else if(n == a[mid]) {

            return mid;
        }
    }

    return -1;
}

[Adak]

I surely don't like it.

I can see having two returns in a function. One is preferred, but two is OK. Four returns in one function, is not OK.

mid should be set in ONE line of code, outside of the if else statements instead of being inside, in two different places.

if(n < a[mid]) should set max to mid-1, instead of mid. n is, after all *less than*, a[mid].

if(length <2) is unnecessary.

Take a peek at one of the good binary search functions, and compare it, with yours. This forum has some good examples.

[creeps]

Coming to think of it, yeah, the code was quite a mess, making everything a challenge to understand. I've rewritten it looking over collective advice, including the above one, and I've come up with the below piece of code. I'm going to add implement a quicksort later, and make the array an user input. Thanks for your feedback!

/**
 *  Author:     Cezar El-Nazli
 *    Date:     Sun, 8th August 2010
 * Purpose:     Minimalistic implementation of the binary search algorithm
 */
 
/* Include the standard I/O header */
#include<stdio.h>

/* Define the number of elements the array has got */
#define SIZE 10

/**
 * int binary_search(int array[], int length, int element)
 *
 * This function takes a sorted array of integers, its length and a target
 * element as arguments. It then searches the array, looking for the target
 * element. It does so by splitting the array into halves, comparing the
 * middle value of the current iteration with the target element. If the
 * element is found, its position is returned. Otherwise, a negative value
 * is returned
 */
int binary_search(int array[], int length, int element);

/**************************************************************************
 * main: this function creates an array of sorted integers, and then asks *
 *       the user for a number. After that, it calls binary_search(),     *
 *       comparing its return value with 0. If the return value is        *
 *       negative, the element has not been found. Otherwise, the return  *
 *       value holds its position within the array                        *
 **************************************************************************/
int main(void) {

    /**
     * int array[N]: an array of N integers in ascending order
     * int n: the number to search the array for
     * int result: the return value of binary_search()
     */
    int array[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n, result;

    /* Get the number */
    printf("Enter a number: ");
    scanf("%d", &n);

    result = binary_search(array, SIZE, n); /* Execute the binary search */

    if(result < 0) {

        printf("The number is not in the array");
    } else {
        
        printf("The element was found at position %d", result);
    }

    printf("\n"); /* Print a new line */

    return 0; /* Return 0 upon successful program execution */
}

/* Define the binary search function */
int binary_search(int a[], int len, int n) {

    /**
     * int min: the lower bound, initially 0
     * int max: the upper bound, initially set to the length of the array
     * int mid: the middle value of the current iteration
     */
    int min = 0, max = len, mid;

    do {

        /* Update the middle value. The method below avoids overflow */
        mid = min + (max - min) / 2;

        /**
         * If the middle value is less than the target value, update the
         * minimum value. If the middle value is greater than the target
         * value, update the maximum value. If the middle value is equal
         * to the target value, return the current value of 'mid'
         */
        if(a[mid] < n) {

            min = mid + 1;
        } else if(a[mid] > n) {

            max = mid - 1;
        } else if(a[mid] == n) {

            return mid;
        }
    } while(min < max);

    /**
     * If the loop didn't exit the function, the target value has not been
     * found. Therefore, the function returns a negative value, dealt with
     * in the main() function above
     */
    return -1;
}

[Adak]

That looks very good!

This is one of the finest examples of Quicksort I've seen. Tested fast, clear, and easy to optimize further, if you wish.

//Quicksort w/o a separate compare or swap function :)
void quicksort(int A[], int lo, int hi) {
  int i, j, pivot, temp;

  if(lo == hi) return; 
  i=lo; 
  j=hi;
  pivot= A[(lo+hi)/2]; //change to (lo +(hi-lo)}/2 and re-test

  /* Split the array into two parts */
  do {    
    while (A[i] < pivot) i++; 
    while (A[j] > pivot) j--;
    if (i<=j) {
      //swap(A, i, j);   //this line works fine.
      /* Oddly, on large N, using swap() gives the same time, as
         using the swap code below */
        temp= A[i];
        A[i]= A[j];
        A[j]=temp;
      i++;
      j--;
    }
  } while (i<=j);
    
  if (lo < j) quicksort(A, lo, j);
  if (i < hi) quicksort(A, i, hi);
}

Enjoy!