二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。
- 算法要求：
- 必须采用顺序存储结构
- 必须按关键字大小有序排列
实现：
int bianrySearch(int nums[], int size, int val)
{
int start = 0;
int end = size - 1;
int index = -1;
while(start <= end)
{
index = (start + end) / 2;
if(nums[index] == val) return index;
else if(nums[index] < val) start = index + 1;
else end = index - 1;
}
return -1; //not found
}
网友评论