分治算法

将一个规模为N的问题分解为k个较小的子问题，这些子问题遵循的处理方式就是互相独立且与原问题相同。

两部分组成：

  • 分(divide):递归解决较小的问题。
  • 治(conquer):然后从子问题的解构建原问题的解。

三个步骤：

  1. 分解(divide):将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。
  2. 解决(conquer):若干子问题规模较小而容易被解决则直接解决，否则递归解决各个子问题。
  3. 合并(Combine):将各个子问题的解合并为原问题的解。

递归实现二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
using namespace std;

//递归实现二分查找
//找到这个值最后一级一级的传递return回来
int BinarySearch(int* arr,int minSub,int maxSub,int num)
{
    if (minSub > maxSub)//无解
    {
        return -1;
    }
    int mid = (minSub + maxSub) / 2;
    if (num == arr[mid])
    {
        return mid;
    }
    else if(num < arr[mid])
    {
        //因为中间数据arr[mid]大于num,所以新的范围从minSub到mid-1
        return BinarySearch(arr, minSub, mid - 1, num);
    }
    else//num > arr[mid]
    {
        //因为num大于中间数据arr[mid],所以新的范围从mid+1到maxSub
        return BinarySearch(arr, mid + 1, maxSub, num);
    }
}

int main(void)
{
    int arr[] = { 5,7,9,11,17,23,48,55,64 };
    //数组-起始位置(数组索引范围)-要查找的值
    int index = BinarySearch(arr,0,8,64);
    cout << index << endl;
    return 0;
}