数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中的二分查找
二分查找是一种通过反复将已排序数组减半来查找所需元素的方法。
此方法从整个数组开始。然后将其减半。如果所需数据值大于数组中间的元素，则考虑数组的上半部分。否则，考虑下半部分。持续进行此操作，直到获得所需数据值或剩余数组为空。
下面给出了一个演示C++中二分查找的程序。
示例
#include
using namespace std;
int binarySearch(int arr[], int p, int r, int num) {
if (p <= r) {
int mid = (p + r)/2;
if (arr[mid] == num)
return mid ;
if (arr[mid] > num)
return binarySearch(arr, p, mid-1, num);
if (arr[mid] < num)
return binarySearch(arr, mid+1, r, num);
}
return -1;
}
int main(void) {
int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int num;
cout << "Enter the number to search: \n";
cin >> num;
int index = binarySearch (arr, 0, n-1, num);
if(index == -1){
cout<< num <<" is not present in the array";
}else{
cout<< num <<" is present at index "<< index <<" in the array";
}
return 0;
}输出
Enter the numberto search 20 20 is present at index 5 in the array
在上面的程序中，`binarySearch()`是一个递归函数，用于使用二分查找在数组中查找所需元素。该函数将数组、其下界和上界以及要查找的数字作为参数。如下所示。
int binarySearch(int arr[], int p, int r, int num)
然后计算数组的中点。如果中点的值等于num，则返回它。如果值大于num，则数组将自身递归调用，下界为p，上界为mid-1。如果值小于num，则数组将自身递归调用，下界为mid+1，上界为r。这可以通过以下代码片段看到。
int binarySearch(int arr[], int p, int r, int num) {
if (p <= r) {
int mid = (p + r)/2;
if (arr[mid] == num)
return mid ;
if (arr[mid] > num)
return binarySearch(arr, p, mid-1, num);
if (arr[mid] < num)
return binarySearch(arr, mid+1, r, num);
}
return -1;
}在`main()`函数中，定义了数组`arr[]`。计算数组的大小并指定要查找的数字。然后调用`binarySearch()`来查找数字的索引。如果`binarySearch()`返回的值为-1，则该数字不在数组中。否则，返回索引值。如下所示。
int main(void) {
int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int num = 33;
int index = binarySearch (arr, 0, n-1, num);
if(index == -1)
cout<< num <<" is not present in the array";
else
cout<< num <<" is present at index "<< index <<" in the array";
return 0;
}
更新于：2021年6月28日
18K+ 浏览量
广告