一起学习交流~

二分查找

算法 laomuji 12个月前 (10-11) 342次浏览 已收录 0个评论

一、什么是二分查找

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。它的时间复杂度为O(log2n)

二、查找过程

首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

比如从1-100,需要找到中间的55,如果循环从头到尾需要找55次
使用二分查找
(1+100) / 2 = 50 50<55 (50+100) / 2 = 75 75>55
(50+75) / 2 = 62 62>55
(50+62) / 2 = 56 56>55
(50+56) / 2 = 53 53<55
(53+56) / 2 = 54 54<55
(54+56) / 2 = 55 55=55
只需要7次就找到这个数字,大大节省了查找的速度
但数字只保证有序,但不保证每一个数字都有
比如1,2,5,6,9
所以,要根据下标来进行实现

三、具体代码

//找到返回下标,没有找到就返回-1
int binarySearch(int nums[],int begin,int end,int value)
{
	if (begin > end)return -1;
	int pos = (begin + end) / 2;
	if (nums[pos] > value)
	{
		//如果当前数字大于要找的数字,说明要找的数字在左边
		//当前位置已经找过了,所以左边要-1
		return binarySearch(nums, begin, pos - 1, value);
	}
	else if (nums[pos] < value)
	{
		//如果当前数字小于要找的数字,说明要找的数字在右边
		//当前位置已经找过了,所以右边要+1
		return binarySearch(nums, pos + 1, end, value);
	}
	else
	{
		//如果不大于也不小于,就表示等于,返回所在的下标
		return pos;
	}
}

int main()
{
	int nums[] = { 1,2,3,5,6,7,9,10,54,97,123,654,1324,9876 };
	cout << "查找9876:" << binarySearch(nums, 0, 13, 9876) << endl;
	cout << "查找1324:" << binarySearch(nums, 0, 13, 1324) << endl;
	cout << "查找1:" << binarySearch(nums, 0, 13, 1) << endl;
	cout << "查找555:" << binarySearch(nums, 0, 13, 555) << endl;
}
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论