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 }
标签:二分,arr,target,int,编程,查找,low,打卡 From: https://www.cnblogs.com/qmz-znv2/p/17402717.html