二分查找算法 c语言二分查找程序代码

出品 | CSDN（CSDNnews）

二分查找，又被称为折半查找（Binary Search），是一种时间复杂度为O(logn)的高效查找算法。它要求被查找的序列必须是有序的。但在这里，我们所说的“有序”究竟意味着什么呢？让我们一起来探讨。

数字的二分查找

我们来简要描述一下二分查找算法的基本思路。

设定一个初始返回值-1，若找不到目标值则返回此值。定义两个指针，left和right，其中left指向序列的第一个元素，right指向序列的最后一个元素。接着，计算中间值mid=(left+right)//2（这里使用整除运算符“//”以避免浮点数计算），然后将中间值arr[mid]与目标值target进行比较。

如果target等于arr[mid]，则说明找到了目标值，直接返回mid作为其下标。

如果target小于arr[mid]，则说明目标值如果存在，一定位于中间值的左边。将right指针置为mid-1，下次查找的序列范围变为[left, mid-1]。

如果target大于arr[mid]，则说明目标值如果存在，一定位于中间值的右边。将left指针置为mid+1，下次查找的序列范围变为[mid+1, right]。

如此循环，直到left>right为止。

二分查找的拓展应用

二分查找不仅仅适用于数字序列，还可以应用于字符串的字典序查找。例如，当面对一个按字典序排列的字符串数组时，我们可以利用字符串的比较规则来进行二分查找。

二分查找峰值

有时，我们面对的序列虽然看似无序，但其中却隐藏着部分有序的规律。例如，在一个峰值左右的元素都比它小或大的数组中，我们可以首先找到峰值的位置，然后再对峰值的左右两侧使用二分查找。

找到峰值后，我们可以分别在峰值的左侧和右侧进行二分查找，以快速定位目标值。

节省时间的小技巧

在二分查找的过程中，我们可以使用位运算中的右移运算符“>>”来计算中间值，这样可以比加法运算更快地得到结果。具体来说，右移一位就相当于除以2。

总结

二分查找是一种利用序列有序性来快速定位目标值的算法。它不仅适用于纯粹的有序序列，还适用于部分有序、有规律可循的序列。只要能够将查找范围不断缩小，就可以考虑使用二分查找算法。

【END】