普通二分法查找元素：
计算
安全
数据库
网络和加速
企业服务
#include <stdio.h>
#include <stdlib.h>
int BinarySearch(int* a, int n, int pos)
{
int left = 0;
int right = n-1;
while (left <= right)
{
int mid = left+(right-left)/2;
if(pos == a[mid])
{
return mid;
}
else if(pos < a[mid])
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return -1;
}
int main()
{
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
int ret = BinarySearch(arr, 10, 5);
printf("pos : %d\n", ret);
system("pause");
return 0;
}
那如果是查找数组中第一次出现的那个元素，这种方法显然是不可行。
就需要修改一小下下
#include <stdio.h>
#include <stdlib.h>
int BinarySearch(int* a, int n, int pos)
{
int left = 0;
int right = n-1;
while (left <= right)
{
int mid = left+(right-left)/2;
if(pos == a[mid])
{
while(mid-1 >= 0 && pos == a[mid-1])
{
mid = mid-1;
}
return mid;
}
else if(pos < a[mid])
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return -1;
}
int main()
{
int arr1[10] = {1,2,3,4,5,6,7,8,9,10};
int arr2[13] = {1,2,3,4,5,5,5,5,6,7,8,9,10};
int ret1 = BinarySearch(arr1, 10, 5);
int ret2 = BinarySearch(arr2, 10, 5);
printf("pos1 : %d\n", ret1);
printf("pos1 : %d\n", ret2);
system("pause");
return 0;
}
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
