C经典算法之二分查找法
1.根据key查找所在数组的位置
?
|
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
|
#include <stdio.h>
/*
key = 9;
1 2 3 4 5 6 7 8
arr 3， 4， 5， 7， 9 ， 11， 21， 23
low = 1 mid = (low + high)/2 = 4 high = 8;
one arr[mid] = 7 < 9; so low = mid + 1 = 5; high = 8; mid = (low + high)/2 = 6
two arr[mid] = 11 > 9 so low = 5 , high = mid - 1 = 5 mid = 5;
arr[mid] = 9 == key
if(key = 10) low = mid + 1 > high
*/
int main(int argc, const char * argv[])
{
int findByHalf(int arr[], int len, int key);
int arr[] = {3, 4 , 5, 7, 9 , 11, 21, 23};
int len = sizeof(arr)/sizeof(int);
int index = findByHalf(arr, len, 88);
printf("index = %d\\n", index);
return 0;
}
int findByHalf(int arr[], int len, int key){
int low = 0;
int high = len - 1;
int mid ;
while(low <= high){
mid = (low + high) / 2;
//右边查找
if (key > arr[mid]) {
low = mid + 1;
//左边查找
}else if (key > arr[mid]) {
high = mid - 1;
}else{
return mid;
}
}
return -1;
}
|
2.插入一个数，得到其所在数组的位置
?
|
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
|
#include <stdio.h>
/*
key = 9;
1 2 3 4 5 6 7 8
arr 3， 4， 5， 7， 9 ， 11， 21， 23
low = 1 mid = (low + high)/2 = 4 high = 8;
one arr[mid] = 7 < 9; so low = mid + 1 = 5; high = 8; mid = (low + high)/2 = 6
two arr[mid] = 11 > 9 so low = 5 , high = mid - 1 = 5 mid = 5;
arr[mid] = 9 == key
if(key = 10) low = mid + 1 > high
*/
int main(int argc, const char * argv[])
{
int findByHalf(int arr[], int len, int key);
int arr[] = {3, 4 , 5, 7, 9 , 11, 21, 23};
int len = sizeof(arr)/sizeof(int);
int index = findByHalf(arr, len, 88);
printf("index = %d\\n", index);
return 0;
}
int insertByHalf(int arr[], int len, int key){
int low = 0;
int high = len - 1;
int mid ;
while(low <= high){
mid = (low + high) / 2;
//右边查找
if (key > arr[mid]) {
low = mid + 1;
//左边查找
}else if (key > arr[mid]) {
high = mid - 1;
}else{
//如果arr[mid] == key
//就把key插入到这个数的后面
return mid + 1;
}
}
//如果low > high 说明 key > arr[mid];
//就把key插入到low对应的 这个数的位置
return low;
}
|
如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
相关文章
猜你喜欢
- 个人服务器网站搭建：如何选择合适的服务器提供商？ 2025-06-10
- ASP.NET自助建站系统中如何实现多语言支持？ 2025-06-10
- 64M VPS建站：如何选择最适合的网站建设平台？ 2025-06-10
- ASP.NET本地开发时常见的配置错误及解决方法？ 2025-06-10
- ASP.NET自助建站系统的数据库备份与恢复操作指南 2025-06-10
