自己写的一个简单的二分查找算法

    二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果xa[n/2],则只要在数组a的右半部搜索x.

    二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

    看了一下《专家编程》，在数组边界计算方面觉得自己有些不太弄得清楚，于是按照自己的理解写了这个简单的二分查找算法，测试可行。

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

#define MAX 8    // 默认数组长度为8，按照从小到大顺序排列

typedef int INT32;
typedef unsigned char UCHAR;
				
					
						
							点击(此处)折叠或打开
						
					
					
						#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 8

typedef int INT32;
typedef unsigned char UCHAR;

INT32 *Half_Search( INT32 *array, INT32 size, INT32 value )
{
    INT32 i, start = 0, mid, end = size - 1;
    static INT32 *p = NULL;

    if( size <= 0 )
    {
        printf( "The array is empty!\n" );
    }
    while( start <= end )
    {
        mid = start + ( end - start )/2;

        if( value == array[mid] )
        {
            return ( p = &array[mid] );
        }
        else if( value < array[mid] )
        {
            end = mid - 1;
        }
        else
        {
            start = mid + 1;
        }

    }
    return NULL;
}
int main()
{
    INT32 *pResult = NULL;
    INT32 array[MAX] = {0};
    INT32 i = 0;
    UCHAR *tmp[MAX] = {""}, str[256] = "";
    INT32 ser_value;

    printf( "Input %d numbers with seprator ',' to create a array :\n", MAX );

    fgets( str, sizeof(str), stdin );
    str[strlen(str)-1] = '\0'; // change the end charactor '\n' to '\0'
    tmp[i] = strtok( str, "," );

    while( NULL != tmp[i] )
    {
        array[i] = atoi( tmp[i] );

        if( MAX-1 == i ) // only save MAX number into the array
        {
            break;
        }
        tmp[++i] = strtok( NULL, "," );

    }

    printf( "Input the number you want to search in the array: " );
    for( i = 0; i < MAX; i++ )
    {
       printf( "%d ", array[i] );
    }
    printf( "\nand Input 'quit' to quit search!\n" );

    while(1)
    {
       fgets( str, sizeof(str), stdin );
       str[strlen(str)-1] = '\0';
     if( 0 == strcmp( str, "quit" ) )
        {
            break;
        }
       ser_value = atoi( str );
       memset( str, 0, sizeof(str) );
       pResult = Half_Search( array, sizeof(array)/sizeof(int), ser_value );

     if( NULL == pResult )
     {
           printf( "Can not find the given number in array!\n");
     }
     else
     {
           printf( "The number %d is in the array! location is %d\n", *pResult,  pResult - array );
     }
    }
    return 0;
}