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

• 总结

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

 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比较无非就三种情况：midk,mid=k。第一种情况，k在mid的右边，我们将low调整为mid+1，high不用调整；第二种情况，k在mid的左边，我们将high调整为mid-1，low不用调整。最后一种情况最简单，我们已经找到了k，直接将mid打印出来就行了，代码如下：

 #include  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  k) { high = mid - 1; } else if (arr[mid] r) printf("没找到，请重新输入"); return 0; } 

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

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注gaodaima搞代码网的更多内容！