折半查找法
程序员文章站
2024-03-20 18:24:52
...
/**
* 折半查找又称二分查找,算法复杂度为O(log(n)),但缺点是要求
* 待查表为有序表,此算法充分利用了数组的有序性,采用分治策略
* 找出待查元素在数组中的位置,若数组中不存在该元素,则返回-1
*/
#include <stdio.h>
int binary_search(int array[], int n, int data)
{
int low = 0, high = n - 1, mid;
while(high >= low)
{
mid = (low + high) / 2;
if(array[mid] == data)
return mid;
else if(array[mid] > data)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
main()
{
int array[] = {1, 5, 30, 41, 100, 101};
printf("%d\n", binary_search(array, 6, 101));
printf("%d\n", binary_search(array, 6, 2));
}
运行结果:
5
-1
转载于:https://my.oschina.net/u/1012872/blog/127146