查找

发表于 | 分类于
顺序查找和二分查找

说明：代码使用codeblocks编译，C++实现，个人编写，如有错误，还望指正。

fengjingtu

二分查找要求输入的数据是有序的。如果有重复的元素，查找到的未必是最前面的。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>

using namespace std;
//顺序查找
//找到返回下标，没找到返回-1；

int order_search(int array[],int len,int val)
{
    for(int i=0;i<len;i++)
    {
        if(array[i]==val)
            return i;
    }
    return -1;
}
//二分查找
//找到返回下标，没找到返回-1；
int binsearch(int array[],int len,int val)
{
    int low=0;
    int high=len-1;
    int mid=0;
    while(low<=high)//注意要有=
    {
        mid=(low+high)/2;
        if(array[mid]==val)
            return mid;
        else if(array[mid]>=val)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;

}

int main()
{
    int a[]={10,11,12,13,14,15,16,17,18,19};
    cout<<order_search(a,sizeof(a)/sizeof(a[0]),13)<<endl;

    cout<<binsearch(a,sizeof(a)/sizeof(a[0]),9)<<endl;
    cout<<binsearch(a,sizeof(a)/sizeof(a[0]),10)<<endl;
    cout<<binsearch(a,sizeof(a)/sizeof(a[0]),11)<<endl;
    cout<<binsearch(a,sizeof(a)/sizeof(a[0]),12)<<endl;
    cout<<binsearch(a,sizeof(a)/sizeof(a[0]),13)<<endl;
    cout<<binsearch(a,sizeof(a)/sizeof(a[0]),14)<<endl;
    cout<<binsearch(a,sizeof(a)/sizeof(a[0]),15)<<endl;
    cout<<binsearch(a,sizeof(a)/sizeof(a[0]),16)<<endl;
    cout<<binsearch(a,sizeof(a)/sizeof(a[0]),17)<<endl;
    cout<<binsearch(a,sizeof(a)/sizeof(a[0]),18)<<endl;
    cout<<binsearch(a,sizeof(a)/sizeof(a[0]),19)<<endl;
    cout<<binsearch(a,sizeof(a)/sizeof(a[0]),20)<<endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
运行结果：

3
-1
0
1
2
3
4
5
6
7
8
9
-1