侧边栏壁纸
  • 累计撰写 278 篇文章
  • 累计创建 3 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

【算法】分治算法

xuanxuan
2021-10-22 / 0 评论 / 0 点赞 / 4 阅读 / 1263 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2024-02-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

分治算法

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

两部分组成

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

三个步骤

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

递归实现二分查找

#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;
}
0

评论区