大神的世界

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

#define SIZE 10

int recursiveBinarySearch(int list[], int key, int left, int right)
{
    if(left > right)
        return -1;

    int middle = (left + right)/2;
    if(key > list[middle])
        recursiveBinarySearch(list, key, middle+1, right);
    else if(key < list[middle])
        recursiveBinarySearch(list, key, left, middle-1);
    else 
        return middle;
}

int BinarySearch(int list[], int key, int n)
{
    int left = 0, right = n;
    int middle;
    while(left <= right){
        middle = (left + right)/2;
        if(key > list[middle])
            left = middle + 1;
        else if(key < list[middle])
            right = middle - 1;
        else
            return middle;
    }
    return -1;
}

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

int main()
{
    srand(time(NULL));

    int list[SIZE+1];
    for(int i = 0; i<=SIZE; i++)
        list[i] = rand()%100;

    qsort(list, SIZE, sizeof(int), compare);
    printf("list: ");
    for(int i = 1; i<=SIZE; i++)
        printf("%d ", list[i]);
    printf("\n");

    int random = rand()%SIZE + 1; // just use list[1~n]
    printf("%d at list[%d]\n", list[random], recursiveBinarySearch(list, list[random], 1, SIZE));
    printf("%d at list[%d]\n", list[random], BinarySearch(list, list[random], SIZE));

    return 0;
}