48 查找

1，在C中，我们常用的查找有两种：

　　①顺序查找

　　②二分查找

2，顺序查找：有一个数列：{ 23，1，34，89，101 }

　　猜数游戏：从键盘中任意输入一个数，判断数列中是否包含该数【顺序查找】

　　如果找到了，就提示找到，并给出下标值。找不到就提示没有

 1 int seqSearch(int arr[],int arrlen,int findval) {
 2     for (int i = 0;i < arrlen;i++) {
 3         if (arr[i] == findval) {
 4             return i;
 5         }
 6     }
 7     return -1;
 8 }
 9 void main() {
10     //按照数组进行遍历，一个一个的比较，如果相等，则找到
11     int arr[] = { 23,1,34,89,101 };
12     int arrlen = sizeof(arr) / sizeof(int);
13     int num = 34;
14     int res = seqSearch(arr, arrlen, num);
15     printf("res=%d", res);//2
16     if (res != -1) {
17         printf("找到了,下标是%d
",res);
18     }
19     else {
20         printf("没有找到");
21     }
22     
23 
24 }

打印结果：找到了，下标是2

第二步，把想要寻找的值变成用户的输入即可：

 1 int seqSearch(int arr[],int arrlen,int findval) {
 2     for (int i = 0;i < arrlen;i++) {
 3         if (arr[i] == findval) {
 4             return i;
 5         }
 6     }
 7     return -1;
 8 }
 9 void main() {
10     //按照数组进行遍历，一个一个的比较，如果相等，则找到
11     int arr[] = { 23,1,34,89,101 };
12     int arrlen = sizeof(arr) / sizeof(int);
13     int num = 0;
14     printf("请输入一个想要寻找的值:");
15     scanf("%d", &num);
16     int res = seqSearch(arr, arrlen, num);
17     printf("res=%d", res);//2
18     if (res != -1) {
19         printf("找到了,下标是%d
",res);
20     }
21     else {
22         printf("没有找到");
23     }
24     
25 }

3，二分查找：请对一个有序数组进行二分查找，{ 1，8，10，89，1000，1234 }，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示没有这个数

　　二分查找的前提是：该数组是一个有序数组

 1 int binarySearch(int arr[], int arrlen, int findval) {
 2     int mid_index = (0 + arrlen - 1) / 2;
 3     int left_index = 0;
 4     int right_index = arrlen - 1;
 5     //注意，要定义没有找到的情况
 6     if (left_index > right_index) {
 7         return -1;
 8     }
 9     //1，当数组的中间值大于目标值，说明在数组左边寻找
10     else if (arr[mid_index] > findval) {
11         for (int i = 0;i < mid_index;i++) {
12             if (arr[i] == findval) {
13                 return i;
14             }
15         }
16         return -1;
17     }
18     //2，当数组的中间值小于目标值，说明在数组的右边寻找
19     else if(arr[mid_index] < findval) {
20         for (int i = mid_index;i <= right_index;i++) {
21             if (arr[i] == findval) {
22                 return i;
23             }
24         }
25         return -1;
26     }
27     //3，数组的中间值等于目标值，找到了
28     else {
29         return mid_index;
30     }
31 }
32 
33 void main() {
34     int arr[] = { 1,8,10,89,1000,1234 };
35     int arrlen = sizeof(arr) / sizeof(int);
36     int num = 0;
37     printf("请输入你想找的数字：");
38     scanf("%d", &num);
39     int res=binarySearch(arr, arrlen, num);
40     printf("res=%d
", res);
41     if (res != -1) {
42         printf("找到了，下标是%d
", res);
43     }
44     else {
45         printf("没有找到");
46     }
47 
48 }

可以使用递归实现二分查找：

 1 int binarySearch(int arr[], int leftIndex,int rightIndex, int findval) {
 2     int midIndex = (leftIndex+rightIndex) / 2;
 3     //注意，要定义没有找到的情况
 4     if (leftIndex > rightIndex) {
 5         return -1;
 6     }
 7     //1，当数组的中间值大于目标值，说明在数组左边寻找
 8     else if (arr[midIndex] > findval) {
 9         binarySearch(arr, leftIndex, midIndex - 1, findval);
10     }
11     //2，当数组的中间值小于目标值，说明在数组的右边寻找
12     else if(arr[midIndex] < findval) {
13         binarySearch(arr, midIndex + 1, rightIndex, findval);
14     }
15     //3，数组的中间值等于目标值，找到了
16     else {
17         return midIndex;
18     }
19 }
20 
21 void main() {
22     int arr[] = { 1,8,10,89,1000,1234 };
23     int arrlen = sizeof(arr) / sizeof(int);
24     int num = 0;
25     printf("请输入你想找的数字：");
26     scanf("%d", &num);
27     int res=binarySearch(arr, 0,arrlen-1,num);
28     printf("res=%d
", res);
29     if (res != -1) {
30         printf("找到了，下标是%d
", res);
31     }
32     else {
33         printf("没有找到");
34     }
35 
36 }