Linux C/C++编程一站式学习中折半查找（如果待查找的元素在数组中有多个则返回第一个）
折半查找
本节的折半查找算法有一个特点：如果待查找的元素在数组中有多个则返回其中任意一个，以本节定义的数组 int a[8] = { 1, 2, 2, 2, 5, 6, 8, 9 }; 为例，如果调用 binarysearch(2) 则返回3，即 a[3] ，而有些场合下要求这样的查找返回 a[1] （如果待查找的元素在数组中有多个则返回第一个）。请修改折半查找算法实现这一特性。
代码
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
| #include <stdio.h>
#define LEN 8
int a[LEN] = { 1, 2, 2, 5, 5, 6, 8, 9 };
int binarysearch(int number)
{
int mid,start = 0,end = LEN - 1;
while(start <= end){
mid = (start + end) / 2;
if(a[mid] < number)
start = mid + 1;
else if(a[mid] > number)
end = mid - 1;
else
for(int j=mid-1;j >= 0;j--)
if(a[j] == a[mid])
mid = j;
return mid;
}
return -1;
}
int main(void)
{
printf("%d\n", binarysearch(5));
return 0;
}
|
![结果截图]
