折半查找

折半查找描述：
从一组从小到大的有序数中查找一个数，查找方法如下：
首先将有序数以中间的那个数分成两组，左半部分和右半部分
将要查找的数和中间的数进行比较，如果大于中间的数，则在右半部分重复上述查找过程；
如果小于中间的数，则在左半部分重复上述过程；
如果等于则表示查找到了。
例如在下面的一组从小到大的有序数中差找3
1   3   8   9   10   11   18   19   30
首先将该组数分成两个部分
1   3   8   9   [10]   11   18   19   30
将3与10进行比较， 3  < 10， 则在左半部分查找
1   3   8   9
将该组数分成两个部分
1   [3]   8   9
将3和3比较，相等，则找到要找的数

再比如要查找20
1   3   8   9   [10]   11   18   19   30
将20和10进行比较，20 > 10，则在右半部分查找
11   [18]   19   30
将20和18比较， 20 > 18， 则在右半部分查找
19 [30]
将20和30比较，20 < 30， 则在左半部分查找
[19]
将20和19进行比较，20 > 19，所有数已经比较完毕，没有找到要查找的数

具体实现方法如下：

/*
File Name :  binsearch.c
Fucntion :   折半查找
Description:
        有n个不同的整数n>=1, 且它们已经排序好放在数组list中，
        list[0] <= list[1] <= .... <= list[n-1]
        现在要查找一个数searchnum是否在list中，如果找到则返回
        在list中的位置，否则返回－1。
        查找过程如下：

        left, right分别表示查找的左右边界，设置初始值left = 0; right = n - 1
       
        当 left <= right 时 (如果left > right 表示没有找到)
        mid = (left + right ) / 2;

        将 searchnum 与 list[mid] 进行比较
        (1) searchnum > list[mid]
              则 查找的数必定在 mid + 1和 n - 1之间，修改left = mid + 1
              重复上述查找过程
        (2) searchnum < list[mid]
              则 查找的数必定在 0 到 mid - 1， 之间，修改right = mid - 1;
              重复上述查找过程
        (3) searchnum == list[mid]
              则 查到要找的数，返回 mid，
              查找过程完毕

*/

#include
#include

#define    MAXNUM        10  /* 有序数的个数 */

void SelSort(int x[], int num);
int  BinSearch(int x[], int num, int left, int right);
int  Compare(int x, int y);

int main(void)
{
    int i, searchnum, pos;
    int a[MAXNUM];

    printf("%d random numbers:\n", MAXNUM);
    for ( i = 0; i < MAXNUM; i++ )
    {
        a[i] = rand() % 1000;
        printf("%7d", a[i]);
    }

    /*用选择排序算法将产生的随机数进行排序*/
    SelSort(a, MAXNUM);
    printf("\n\nAfter Selection Sort:\n\n");
    for ( i = 0; i < MAXNUM; i++ )
        printf("%7d", a[i]);

    printf("\n\nPlease input the number you want to search: \n");
    scanf("%d", &searchnum);
    printf("\nThe num you search is : %d\n\n", searchnum);

    // 调用折半查找算法查找要找的数
    pos = BinSearch(a, searchnum, 0, MAXNUM -1);
    if ( pos == -1 )
        printf("Not Found the search num : %d\n", searchnum);
    else
        printf("\n\nSearch Result: a[%d] = %d\n", pos, a[pos]);
   
    return 0;
}

/* 选择排序
   关于选择排序具体算法详见
   http://blog.chinaunix.net/u/5391/showart_240805.html
*/
void SelSort(int x[], int num)
{
    int i, j, temp;

    for ( i = 0; i < num － 1; i++ )
    {
        for ( j = i + 1; j < num; j++ )
        {
            if ( x[i] > x[j] )
            {
                temp = x[i];
                x[i] = x[j];
                x[j] = temp;
            }
        }
    }
}

/* 折半查找算法
   x        为从小到大的一组有序整数
   num      为要查找的整数
   left     为查找左边界
   right    为查找右边界
*/
int BinSearch(int x[], int num, int left, int right)
{
    int mid;
   
    if ( left <= right )
    {
        mid = (left + right) / 2; // 计算中间边界
        // 比较要查找的数和中间的那个数
        switch(Compare(x[mid], num))
        {
        case 0: // 相等
            return mid;
        case 1: // 要查找的数小于中间的那个数
            return BinSearch(x, num, left, mid - 1); // 递归调用
        case -1: // 要查找的数大于中间的那个数
            return BinSearch(x, num, mid + 1, right);
        }
    }

    return -1;
}

/*
  比较两个整数x和y的大小
  如果 x > y 返回 1
  如果 x < y 返回 -1
  如果 x == y 返回 0
*/
int Compare(int x, int y)
{
    if ( x > y )
        return 1;
    else if ( x < y )
        return -1;
    else return 0;
}