二分查找算法，也称为折半查找算法，是一种在有序数组中查找特定元素的常用算法，用于在有序数组或列表中查找特定元素的位置。它的基本思想是：首先确定目标值可能存在的区间，然后逐步缩小区间直到确定目标值的位置或者确定目标值不存在。
一、二分查找算法的原理：
- 前提条件：待查找的数组必须是有序的，通常是按照升序排列。
- 比较中间元素：在每一次迭代中，算法计算数组的中间索引，并将目标值与中间元素进行比较。
- 缩小查找范围：如果目标值小于中间元素，则目标值必定位于中间元素的左侧；如果目标值大于中间元素，则目标值必定位于中间元素的右侧。
- 重复查找：根据比较结果，将查找范围缩小为左侧或右侧的子数组，并重复上述步骤，直到找到目标值或查找范围为空为止。
具体步骤如下：将数组按照元素值的大小进行排序，使得数组元素呈有序状态。
- 初始化两个指针low和high，分别指向数组的起始位置和结束位置。
- 在每一次循环中，计算中间位置mid=(low+high)/2，并取得中间位置的元素值。
- 如果中间位置的元素值与目标值相等，则找到了目标值，返回中间位置。
- 如果目标值小于中间元素，则更新右边界为中间索引减一：
right = mid - 1； - 如果目标值大于中间元素，则更新左边界为中间索引加一：
left = mid + 1。 - 如果low大于high，说明目标值不存在于数组中，返回不存在的标识。
二分查找算法的时间复杂度为O(logN)，其中N为数组的长度。由于二分查找算法每次查找都将区间长度减半，因此其效率较高。
需要注意的是，二分查找算法只适用于有序数组，如果数组是无序的，则需要先进行排序操作。另外，二分查找算法也只适用于静态查询，即查询操作比较频繁，而修改操作较少的情况下。如果需要频繁进行插入、删除等修改操作，建议采用其他数据结构。
二、二分查找算法的特点：
- 时间复杂度：O(log n)，其中 n 是数组的长度。
- 空间复杂度：O(1)，仅使用了常量级的额外空间。
- 优点：查找效率高，尤其适用于大规模数据集。
- 缺点：要求数组必须有序，并且不适用于动态变化的数据集。
三、二分查找的示例
#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
// 如果找到目标元素，返回索引
if (arr[mid] == target) {
return mid;
}
// 如果目标元素在左半边，继续在左半边进行二分查找
if (arr[mid] > target) {
right = mid - 1;
}
// 如果目标元素在右半边，继续在右半边进行二分查找
else {
left = mid + 1;
}
}
// 如果没有找到目标元素，返回-1
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11}; //初始化一个一维数组
int n = sizeof(arr) / sizeof(arr[0]);
int target = 7;
int result = binarySearch(arr, 0, n - 1, target);//调用二分查找函数binarySearch()
if (result == -1) {
cout << "目标值 " << target << " 未找到";
} else {
cout << "目标值 " << target << " 在索引 " << result << " 处找到";
}
return 0;
}
感谢各位读者的阅读与支持，您的支持是我前进的动力！我希望我的博文能够带给您有益的信息和启发，让您的生活更加丰富多彩。如果您有任何问题或意见，请随时联系我或在评论区评论。再次感谢您的支持！希望以上示例对大家有帮助，如有疑问，欢迎您在评论区评论，谢谢！！！
标签：二分,int,元素,算法,查找,数组,目标值 From： https://blog.csdn.net/m0_75068978/article/details/139318710