C语言折半查找法介绍及使用示例
什么是折半查找法
折半查找法(也称二分查找法)是一种常用的查找算法。它是根据定位元素与查找范围中间元素的比较结果,将查找范围逐渐缩小,最终定位到所查找的元素的过程。
其基本思路可以用以下伪代码表示:
// array是一个已经按照从小到大排序好的数组,n是数组长度,x是要查找的元素
binary_search(array, n, x) {
left = 0, right = n - 1
while (left <= right) {
mid = (left + right) / 2
if (array[mid] == x)
return mid
else if (array[mid] < x)
left = mid + 1
else
right = mid - 1
}
return -1
}
折半查找法的时间复杂度
折半查找法的时间复杂度为$O(\log n)$,其中$n$表示查找范围中元素的个数。这意味着,随着查找范围的增大,折半查找法的效率将会迅速提高。
使用折半查找法的步骤
使用折半查找法的步骤大致如下:
- 将要查找的元素与查找范围中间的元素比较。
- 如果它们相等,则查找结束,返回该元素的位置。
- 如果要查找的元素比中间的元素小,则在查找范围的左半部分继续查找。
- 如果要查找的元素比中间的元素大,则在查找范围的右半部分继续查找。
- 重复以上步骤,直到找到要查找的元素或查找范围为空。
折半查找法的示例
以下是两个使用折半查找法的示例。
示例 1:查找一个整数是否存在于已排序的整数数组中
假设我们有一个已经按照从小到大排序好的整数数组arr
,长度为n
。我们需要编写一个函数来判断给定的整数x
是否在该数组中存在,如果存在,则返回它的位置,否则返回-1。
可以使用折半查找法来实现上述功能。代码如下:
int binary_search(int arr[], int n, int x) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == x)
return mid;
else if (arr[mid] < x)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
示例 2:查找一个字符串是否存在于已排序的字符串数组中
假设我们有一个已经按照从小到大排序好的字符串数组str_arr
,长度为n
。我们需要编写一个函数来判断给定的字符串str
是否在该数组中存在,如果存在,则返回它的位置,否则返回-1。
可以使用折半查找法来实现上述功能。代码如下:
int binary_search(char *str_arr[], int n, char *str) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
int cmp = strcmp(str_arr[mid], str);
if (cmp == 0)
return mid;
else if (cmp < 0)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
注意,对于字符串数组的折半查找,我们需要使用strcmp
函数来进行字符串的比较。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C语言折半查找法介绍及使用示例 - Python技术站