小浩浩（小浩浩玩游戏）

  1 #include <iostream>
  2 using namespace std;
  3 
  4 /************************************************************************/
  5 /* @brief 二分查找非递归实现
  6 /* @param arr非递减数组
  7 /* @param start数组查找范围起始下标
  8 /* @param end数组查找范围结束下标
  9 /* @param key需要查找的值
 10 /* @return key在数组中的下标 -1表示没有查找到
 11 /************************************************************************/
 12 int binarySearch(const int* arr, int start, int end, const int key)
 13 {
 14     int index = -1;
 15     //如何传入的参数有问题，直接返回-1，查找失败
 16     if (arr == nullptr || start < 0 || end < start)
 17     {
 18         return index;
 19     }
 20 
 21     while (end >= start)
 22     {
 23         int middle = (end - start) / 2 + start;
 24         //查找到
 25         if (arr[middle] == key)
 26         {
 27             index = middle;
 28             break;
 29         }
 30         //查找的值比中间的值小，说明在前半部分
 小浩浩 31         else if (arr[middle]  > key)
 32         {
 33             end = middle - 1;
 34         }
 35         //查找的值比中间的值大，说明在后半部分
 36         else
 37         {
 38             start = middle + 1;
 39         }
 40     }
 41     return index;
 42 }
 43 
 44 /************************************************************************/
 45 /* @brief 二分查找递归实现
 46 /* @param arr非递减数组
 47 /* @param start数组查找范围起始下标
 48 /* @param end数组查找范围结束下标
 49 /* @param key需要查找的值
 50 /* @return key在数组中的下标 -1表示没有查找到
 51 /************************************************************************/
 52 int binarySearchR(const int* arr, int start, int end, const int key)
 53 {
 54     int index = -1;
 55     //如何传入的参数有问题，直接返回-1，查找失败
 56     if (arr == nullptr || start < 0 || end < start)
 57  小浩浩    {
 58         return index;
 59     }
 60 
 61     int middle = (end-start) / 2 + start;
 62     //查找到
 63     if (arr[middle] == key)
 64     {
 65         index = middle;
 66     }
 67     //查找的值比中间的值小，说明在前半部分
 68     else if (arr[middle] > key)
 69     {
 70         return binarySearchR(arr, start, middle - 1, key);
 71     }
 72     //查找的值比中间的值大，说明在后半部分
 73     else
 74     {
 75         return binarySearchR(arr, middle + 1, end, key);
 76     }
 77 
 78     return index;
 79 }
 80 
 81 int main()
 82 {
 83     int arr[8] = { 0, 1, 7, 9, 11, 13, 18, 19 };
 84 
 85     cout << "原始数据:" << endl;
 86 
 87     for (int i = 0; i < sizeof(arr) / sizeof(int); ++i)
 88     {
 89         cout << arr[i] << "  ";
 90     }
 91 
 92     int key = 18;
 93 
 94     cout << endl << "查询结果:" << endl;
 95 
 96     int index = binarySearch(arr, 0, 7, key);
 97 
 98     cout << "非递归查找" << key << ":" << index << endl;
 99 
100     index = binarySearchR(arr, 0, 7, key);
101 
102     cout << "递归查找" << key << ":" << index << endl;
103 
104     return 0;
105 }