牵着老婆满街逛

严以律己,宽以待人. 三思而后行.
GMail/GTalk: yanglinbo#google.com;
MSN/Email: tx7do#yahoo.com.cn;
QQ: 3 0 3 3 9 6 9 2 0 .

折半查找(二分查找)

最基本的算法:
int BinarySearch(int arr[], int len, int searchKey)
{
    int start = 0, end = len - 1, mid;
    while (start <= end)
    {
        // 求中间的索引值
        mid = (start + end) / 2;

        if (arr[mid] == number)
        {
            // 查到了
            return mid;
        }
        else if (arr[mid] < searchKey)
        {
            // 搜索范围缩小到后半部
            start = mid + 1;
        }
        else if (arr[mid] > searchKey)
        {
            // 搜索范围缩小到前半部
            end = mid - 1;
        }
    }

    // 没查到
    return -1;
}


用到递归的算法:
int BinarySearch( const int arr[], int searchKey, int start, int end )
{
    // 求中间的索引值
    int mid = ( start + end ) / 2;

    if ( searchKey == arr[ mid ] )
    {
        // 找到了
        return mid;
    }
    else if ( searchKey < arr[ mid ] )
    {
        // 搜索范围缩小到前半部
        return BinarySearch( arr, searchKey, start, mid - 1 );
    }
    else if ( searchKey > arr[ mid ] )
    {
        // 搜索范围缩小到后半部
        return BinarySearch( arr, searchKey, mid + 1, end );
    }
    else
    {
        // 没有查找到
        return -1;
    }
}


使用迭代实现:
int BinarySearch( const int arr[], const int& len, const int& searchKey )
{  
    int start=0, end=len-1, mid;
    while ( start < end )
    {
        mid = (start + end) / 2;

        if ( searchKey > arr[mid] )
        {
            start = mid + 1;
        }
        else
        {
            end = mid;
        }
    }

    if ( start > end )
    {
        return -1;
    }
    else
    {
        if ( searchKey == arr[start] )
        {
            return start;
        }
        else
        {
            return -1;
        }
    }
}



测试代码:
void testBinarySearch()
{
    const int LEN = 8;
    int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };

    printf("查找到的索引号为:%d\n", BinarySearch(a, LEN, 5));

    printf("查找到的索引号为:%d\n", BinarySearch(a, 5, 0, LEN-1));
}

posted on 2010-06-02 23:21 杨粼波 阅读(591) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理