打卡 c语言趣味编程二分查找算法实现

qmz-znv2 / 2023-05-15 / 原文

N个有序整数数列已放在一维数组中，利用二分查找法查找整数在数组中的位置。若找到，则输出其下标值；反之，则输出“Not be found!”。

思路：

　　二分查找法（也叫折半查找）其本质是分治算法的一种。所谓分治算法是指的分而治
之，即将较大规模的问题分解成几个较小规模的问题，这些子问题互相独立且与原问题相
同，通过对较小规模问题的求解达到对整个问题的求解。我们把将问题分解成两个较小问
题求解的分治方法称为二分法。需要注意的是，二分查找法只适用于有序序列。
　　二分查找的基本思想是：每次查找前先确定数组中待查的范围，假设指针low和
high(low<high)分别指示待查范围的下界和上界，指针mid指示区间的中间位置，即mid=
(low+high)/2,把m与中间位置(mid)中元素的值进行比较。如果m的值大于中间位置元
素中的值，则下一次的查找范围放在中间位置之后的元素中；反之，下一次的查找范围放
在中间位置之前的元素中。直到low>high,查找结束。

流程图：

代码实现：

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 // 二分查找函数
 7 int binarySearch(const vector<int>& arr, int target) {
 8     int left = 0;
 9     int right = arr.size() - 1;
10 
11     while (left <= right) {
12         int mid = left + (right - left) / 2;
13 
14         if (arr[mid] == target) {
15             return mid; // 找到目标元素，返回下标值
16         } else if (arr[mid] < target) {
17             left = mid + 1; // 目标元素在右半部分
18         } else {
19             right = mid - 1; // 目标元素在左半部分
20         }
21     }
22 
23     return -1; // 没有找到目标元素
24 }
25 
26 int main() {
27     vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15}; // 有序数组
28     int target = 7; // 要查找的目标元素
29 
30     int index = binarySearch(arr, target);
31 
32     if (index != -1) {
33         cout << "Element found at index: " << index << endl;
34     } else {
35         cout << "Not be found!" << endl;
36     }
37 
38     return 0;
39 }