一篇文章带你了解C语言二分查找

编辑: admin 分类: c#语言 发布时间: 2022-03-15 来源:互联网
目录
  • 总结

我们常常需要对数据进行查找,修改,查找数据有许多方法,我们先看看最简单的顺序查找

int main()
{
	int i, k = 0;
	scanf("%d", &k);
	int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (i = 0; i < sz; i++)
	{
		if (arr[i] == k)
		{
			printf("找到了,它是%d", arr[i]);
		}
	}
	return 0;
}

顺序查找绝大多数情况有效但是由于它是一个一个元素进行查找,其效率很低,只有一个for循环所有其时间复杂度为O(n)。我们希望有一个更高效的查找方法,接下来便是二分查找,先来看看一个顺序查找和二分查找的直观比较。

从上面的图中我们感受到二分查找的关键:找到最左边元素(low)和最右边元素(high),确定中间元素(mid),比较中间元素(mid)和目标元素(k)的大小,调整low和high,再确定新的mid....我们要不断确定mid直到找到k,自然需要用到循环,我们有明确的目标:找到k。因此选择while循环,找到k后循环不再进行,而当low和high之间还有元素,即low在high的左边或与之重合,k就依然可能存在,所以循环条件为low<=high,接下来的问题在于怎样调整low和high的值,mid和k比较无非就三种情况:mid<k,mid>k,mid=k。第一种情况,k在mid的右边,我们将low调整为mid+1,high不用调整;第二种情况,k在mid的左边,我们将high调整为mid-1,low不用调整。最后一种情况最简单,我们已经找到了k,直接将mid打印出来就行了,代码如下:

#include <stdio.h>
int main()
{
	int k = 0;
	scanf("%d", &k);
	int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int sz = sizeof(arr) / sizeof (arr[0]);
	int low = 0;
	int high = sz-1;
	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (arr[mid] > k)
		{
			high = mid - 1;
		}
		else if (arr[mid] < k)
		{
			low = mid + 1;
		}
		else
		{
			printf("找到了,它是:%d", arr[a]);
			break;
		}
	}
	if (l>r)
		printf("没找到,请重新输入");
	return 0;
}

二分查找的时间复杂度的问题:总共有n个元素,每次查找的区间大小就是n,n/2,n/4,…,n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数。由于n/2^k取整后>=1,即令n/2^k=1,可得k=log2n,(是以2为底,n的对数),所以时间复杂度可以表示O(logn),确实比顺序查找快不少,但是二分查找有一个较大的局限性:只能查找有序数组的元素,即组数字必须是升序或降序。

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注海外IDC网的更多内容!

【文章原创作者:香港云服务器 http://www.558idc.com/ne.html 复制请保留原URL】