每天学习一个基础算法之二分查找

ops/2024/10/22 23:30:52/

目录

前言：

1、对二分查找概念的诠释

2、二分查找的使用场景

3、对比顺序查找与二分查找时间复杂度

4、二分查找的实现代码

代码主体（以接口函数的形式）

实现思路：

测试部分（主函数调用）

调试结果

前言：

前一篇博客我们已经介绍学习了顺序查找法，它在对有序数据查找时效率较低，而当我们要对有序数据进行查找时就要用到二分查找法了，所以今天我们要学习的就是二分查找法。

1、对二分查找概念的诠释

二分查找也称折半查找，二分查找从数据结构的中间位置开始，如果中间位置的数据正好与给定数据相同，则查找成功；否则利用中间位置将数据分成前后两个部分，如果中间元素大于给定的数据，则继续在前一半数据中查找，否则继续在后一半数据中查找，重复此操作，直到找到与给定数据相同的数据或全部数据找完。

2、二分查找的使用场景

二分查找比顺序查找的效率高，但它必须要求待查找的数据的结构是有序排列的，适用于不经常变动且查找频率较高的有序数据。

3、对比顺序查找与二分查找时间复杂度

顺序查找上篇博客已经说了其本质上就是对数组进行遍历，所以顺序查找的时间复杂度为O(N)，而二分查找的时间复杂度为O(log2n)，这意味着在最坏的情况下，算法的执行时间与以2为底的目标值的对数成正比，这使得二分查找在处理大规模数据时非常高效。

4、二分查找的实现代码

代码主体（以接口函数的形式）

//二分查找法的实现
static int binary_seek(int arr[], int sz, int target)
{int left = 0;int right = sz - 1;while (left <= right){int mid = (left + right) / 2;if (arr[mid] > target){right = mid - 1;}else if (arr[mid] < target){left = mid + 1;}else{return mid;}}return -1;
}

实现思路：

和前一篇博客顺序查找相同，我采取的方式仍为若找到与给定值相同的数据，返回其下标，若最终找完所有数据还没找到则返回-1。

在程序中，我用left代表排查数据段首元素地址；用right代表排查数据段末尾元素地址;用mid代替排查数据段中间元素地址。

根据概念的理解

如果中间位置的数据正好与给定数据相同对应：

return mid;

如果中间元素大于给定的数据，则继续在前一半数据中查找对应：

right = mid - 1;

否则继续在后一半数据中查找对应：

left = mid + 1;

测试部分（主函数调用）

int main()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };int sz = sizeof(arr) / sizeof(arr[0]);int ret = binary_seek(arr, sz, 7);if (ret != -1){printf("下标为%d\n", ret);}else{printf("没找到！\n");}return 0;
}