二分法

以下是我第一次写的二分法c

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
int search(int key,int a[],int length){
    int left=0;
    int right=length-1;
    int sem = -1; //设置变量判断
    while (right > left){
        int x = (left + right)/2；  //x为数组中间的值（mid）
        if (a[x]==key){
            sem = 1;
        }else if (a[x]<key){
          left = x + 1;
        } else {
            right = x - 1;  //二分法分
        }
    }return sem;
}
int main (){
    int a[]={0,6,7,9,15,36,99,445,236}；
    int key;
    scanf("%d",&key);
    int length = sizeof(a)/sizeof(a[0]);
    int sem = search(key,a,length);
        if (sem == 1){
            printf("%d在数组中\n",key);
        }else {
            printf("%d不在数组中\n",key);
        }return 0;
}

发现无论输入任何数字；返回结果均是不在数组；

我的错误

发现 即使我们找出了那个我们需要找出的那个数后，search函数里的while循环仍然会继续走下去，所以我们需要在a[x]==key 成立之后 ，跳出循环即在a[x]==key之后，break；跳出循环。

1
2
3
4
if (a[x]==key){
    sem = 1 ;
    break;
}

此时我们尝试6，7，9发现其都在数组当中；当我输入0时发现其有不在数组当中了；可以看出对于边缘值仍然存在些许的问题；

调试发现存在一种可能，当x(mid)=1时，根据条件：right = x-1，那么此时 right = left = 0；不满足条件；故结束了while循环，所以发现时循环判断出现了问题； 

1
while (right >= left)

那么最后二分法：

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
#include <stdio.h> 
int search(int key,int *a,int length){
    int left=0;
    int right=length-1;
    int sem = -1; //设置变量判断
    while (right >= left){
        int x = (left + right)/2 ; //x为数组中间的值（mid）
        if (a[x]==key){
            sem = 1;
            break;
        }else if (a[x]<key){
          left = x + 1;
        } else {
            right = x - 1;  //二分法分
        }
    }return sem;
}
int main (){
    int a[]={0,6,7,9,15,36,99,445,536};
    int key;
    scanf("%d",&key);
    int length = sizeof(a)/sizeof(a[0]);
    int sem = search(key,a,length);
        if (sem == 1){
            printf("%d在数组中\n",key);
        }else {
            printf("%d不在数组中\n",key);
        }return 0;
}