1. 二分法查找
二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。
二分法查找的思路如下：
(1)首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。
(2)如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤(1)的操作。
(3)如果某一步数组为空，则表示找不到目标元素。
二分法查找的时间复杂度O(logn)。
2. 算法实现
unsigned int binarySearch(unsigned char *data, unsigned int len,unsigned char key)
{
unsigned int start=0;
unsigned int mid=0;
unsigned int end=len-1;
while(start<=end)
{
mid = (end+start)/2;
if(key<data[mid])
{
end = mid -1;
}
else if(key>data[mid])
{
start = mid + 1;
}
else
{
return mid;
}
return len; /*out of range*/
}
}
3. 测试
int main()
{
unsigned char srcData[8]={1,2,3,4,5,6,7,8};
unsigned int result;
printf("Hello liudulab!\n");
result = binarySearch(srcData,sizeof(srcData),4);
printf("Search Result: %d\n",result);
result = binarySearch(srcData,sizeof(srcData),10);
printf("Search Result: %d\n",result);
return 0;
}
-----------------END-----------------
