二分查找面试算法题

1.二分查找（有序数组）

https://blog.csdn.net/qq_63918780/article/details/122527681

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int func(int *a,int j,int x)
 5 {
 6     int len = j - 1,i = 0,min;
 7     while(i<len)
 8     {
 9        min = (i+len)/2;
10        if(a[min] > x)
11        {
12           len = min-1;
13        }
14        else if(a[min] < x)
15        {
16           i = min+1;
17        }
18        else
19        {
20           break;
21        }
22     }
23     return min;
24 }
25 
26 int main() 
27 {
28     int j,x,num;
29     int a[] = {1,2,3,4,5,6,7,8,9};
30     printf("输入要查找的数/n");
31     scanf("%d",&x);
32     j = sizeof(a)/sizeof(a[0]);
33     num = func(a,j,x);
34     printf("要查找的数为a[%d]/n",num);
35     
36     return 0;
37 }

2.搜索二维矩阵

https://blog.csdn.net/qq_47406941/article/details/110091759

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。

• 每行的第一个整数大于前一行的最后一个整数。

 1 #include <stdio.h>
 2 
 3 #define N 3
 4 #define M 4
 5 
 6 int main()
 7 {
 8     int x,i = 0,j = M -1;
 9     int a[N][M] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
10     printf("输入一个要查找的数/n");
11     scanf("%d",&x);
12     while(1)
13     {
14         if(x == a[i][j])
15         {
16             printf("找到了/n");
17             break;
18         }
19         else if(x > a[i][j])
20         {
21             if(i < N-1)
22             {
23                 i++;
24             }
25             else
26             {
27                 printf("没找到/n");
28                 break;   
29             }
30         }
31         else
32         {
33             if(j > 0)
34             {
35                 j--;
36             }
37             else
38             {
39                 printf("没找到/n");
40                 break;   
41             }
42         }
43     }
44 
45     return 0;
46 }

3.旋转数组最小数

把一个数组的最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。

例如，数组{3，4，5，1，2}为{1，2，3，4，5}的一个旋转，该数组的最小值为1。

https://blog.csdn.net/weixin_43804406/article/details/107956124 

1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int top(int *a,int len)
 5 {
 6    int i,j = a[0];
 7    for(i = 0;i<len;i++)
 8    {
 9        if(j > a[i])
10        {
11            return a[i];
12        }
13    }
14    return -1;
15 }
16 
17 int func(int *a,int len)
18 {
19     int i = 0,j = len - 1,min;
20     while(i<=j)
21     {
22         min = (i+j)/2;
23         
24         if(a[min] == a[i] && a[min] == a[j])
25         {
26             return top(a,len);
27         }
28         
29         if(a[min] > a[i])
30         {
31             i = min+1;
32         }
33         else if(a[min] < a[j])
34         {
35             j = min-1;
36         }
37         else
38         {
39             break;
40         }
41     }
42     return a[min];
43 }
44 
45 int main() 
46 {
47     int a[] = {3,4,5,1,2};
48     int len = sizeof(a)/sizeof(a[0]);
49     int i = func(a,len);
50     printf("%d/n",i);
51     
52     return 0;
53 }