C/C++ 二分查找面试算法题
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 34 #define M 45 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 }4.搜索旋转排序数组
https://blog.csdn.net/jakercl/article/details/125586657
整数数组 nums 按升序排列，数组中的值互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，
使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0 开始计数）。
例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你旋转后的数组 a 和一个整数 x，如果 nums 中存在这个目标值 x ，则返回它的下标，否则返回 -1 。
必须设计一个时间复杂度为 O(logn) 的算法解决此问题
1 #include <stdio.h>2 #include <stdlib.h>3 4 #define N 95 6 int func(int a[])7 {8 int i = 0,j = N-1,min,x;9 printf("输入要查找的数字\n");
10 scanf("%d",&x);
11 while(i<=j)
12 {
13 min = (i+j)/2;
14 if (a[min] == x)
15 {
16 return min;
17 }
18 if (a[i] <= a[min]) //如果左半区间有序
19 {
20 if (a[i] <= x && x < a[min])//目标值在左侧
21 {
22 j = min - 1;
23 }
24 else//目标值在右侧
25 {
26 i = min + 1;
27 }
28 }
29 else
30 { //如果右半区间有序
31 if (a[min] < x && x <= a[j])//目标值在右侧
32 {
33 i = min + 1;
34 }
35 else//目标值在左侧
36 {
37 j = min - 1;
38 }
39 }
40 }return -1;
41 }
42
43 int main()
44 {
45 int a[N] = {5,6,7,8,9,1,2,3,4};
46 int i = func(a);
47 printf("输入的数字的坐标为a[%d]\n",i);
48
49 return 0;
50 }5.搜索插入位置
https://blog.csdn.net/m0_61465701/article/details/122599140
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:
输入: nums = [1], target = 0
输出: 0
1 #include <iostream>2 #include <vector>3 using namespace std;4 5 class node{6 public:7 int searchinsert(vector<int>& nums,int target){8 int l = 0,r = nums.size() - 1;9 while(l<r){
10 int mid = l + (l+r)/2;
11 if(nums[mid]>=target) r = mid;
12 else l = mid +1;
13 }
14 return r;
15 }
16 };
17
18 int main()
19 {
20 node n;
21 vector<int> cur = {1,2,4,6,8,9};
22 cout << n.searchinsert(cur,3) << endl;
23
24 return 0;
25 }6.c++实现X的平方根（力扣69题）
1 #include <iostream>2 using namespace std;3 4 class node1{5 public:6 int mysqrt(int x){7 int l = 0,r = x;8 while(l<r){9 int min = l + (r-l)/2 +1;
10 if(min*min <= x) l = min;
11 else r = min -1;
12 }
13 return l;
14 }
15 };
16
17 int main()
18 {
19 int x = 6;
20 node1 n;
21 cout << n.mysqrt(x) << endl;
22
23 return 0;
24 }