首页 > 代码库 > 用C++实现二分查找

用C++实现二分查找

2024-09-06 16:38:34   215人阅读

用C++实现二分查找

　　对于有序表而言，通常使用二分查找来寻找待查记录。二分查找，又名折半查找，具体查找过程为：先确定待查找记录的范围，然后逐步缩小范围知道找到或者找不到该记录为至。其C++实现代码如下所示：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 /*二分查找：
 5  array：待查找的数组
 6  low：数组的第一个待查找的位置，通常为0
 7  high：数组的长度-1
 8  searchTarget：待查找的记录*/
 9 int BinSearch (int array[], int low, int high, int searchTarget)
10 {
11     while (low <= high)
12     {
13         int mid = (low + high) / 2;
14         if (searchTarget < array[mid])//待查找的记录在前半段
15         {
16             high = mid - 1;
17         }
18         else if (searchTarget > array[mid])//待查找的记录在后半段
19         {
20             low = mid + 1;
21         }
22         else
23         {
24             return mid;//找到
25         }
26     }
27     return -1;//未找到
28 }
29 
30 int main ()
31 {
32     int a1[6] = {1, 3 ,5, 8, 11, 28};
33     int targetLoc = BinSearch (a1, 0, 7, 5);
34     cout << "元素5在a1中的位置为(编号从０开始, -1表示未找到)： " << targetLoc << endl;
35     int a2[5] = {2, 3, 6, 7, 10};
36     targetLoc = BinSearch (a2, 0, 5, 5);
37     cout << "元素5在a2中的位置为(编号从０开始，-1表示未找到)： " << targetLoc << endl;
38     return 0;
39 

可以看到我们找到了记录５在数组ａ１中的位置，不能找到其在ａ２中的位置，以下是程序的运行结果：
元素5在a1中的位置为(编号从０开始, -1表示未找到)： 2
元素5在a2中的位置为(编号从０开始，-1表示未找到)： -1

 

用C++实现二分查找


联系
我们