现在的位置: 首页 > 13 数据结构入门 > 正文

折半查找法

2013年01月06日 13 数据结构入门 ⁄ 共 356字 ⁄ 字号 暂无评论

折半查找法是高效的查找方法,但前提是所有顺序必须按照关键字来排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
 
int BinarySearch(int v[ ], int n, int x)
{
    int low=0, high=n-1, mid;
    while (low <= high) {
        mid = (low+high)/2;
        if (x < v[mid])
            high = mid - 1;
        else if (x > v[mid])
            low = mid + 1;
        else /* found match */
            return mid;
    }
    return -1;  /* no match */
}
 
int main()
{
    int i, n, v[10]= { 1, 3, 4, 5,  12, 16, 19, 20, 21, 33};
    scanf("%d", &n);
    i = BinarySearch(v, 10, n);  /* 在长度为10的数组 v 中搜索 n */
    if (i==-1)
        printf("Not Found\n");
    else
        printf("%d is at position %d\n", n, i);
    return 0;
}

抱歉!评论已关闭.