五大常规算法：分治法

科技前沿 • 2025-04-05 18:31 • 阅读 35

大家好，我是讯享网，很高兴认识大家。

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

例如，一个袋子中有16枚硬币，其中有一枚是伪造的，伪造的硬币与真硬币相比要轻，现有一台天平，请你在尽可能短的时间内找出那枚伪造的硬币。

常规思维可以每次从硬币中取出两枚比较，如果天平平衡则继续比较

讯享网

利用分治法的思想，我们可以将16枚硬币分为两组。每组8个，分别重，将轻的那一组继续五五分进行称重，这样不管伪造硬币在那个位置，只需要进行4次便可找出。

有一种查找方法名为“二分查找”，它就是利用分治法思想，将规模为N的问题化为k个子问题解决。

二分查找算法实现

#include <stdio.h> #include <stdlib.h> /*递归实现二分查找 参数: arr - 有序数组地址 arr minSub - 查找范围的最小下标 minSub maxSub - 查找范围的最大下标 maxSub num - 带查找数字 返回:找到则返回所在数组下标，找不到则返回-1 */ int BinarySearch(int* arr, int minSub, int maxSub, int num) { if (minSub > maxSub) { return -1;//找不到 num 时,直接返回 } int mid = (minSub + maxSub) / 2; if (num < arr[mid]) { return BinarySearch(arr, minSub, mid - 1, num); } else if (num > arr[mid]) { return BinarySearch(arr, mid + 1, maxSub, num); } else { return mid;//找到 num 时直接返回 } } int main(void) { int arr[] = { 1, 3, 7, 9, 11 }; int index = BinarySearch(arr, 0, 4, 9); printf("index: %d\n", index); system("pause"); return 0; }

讯享网

五大常规算法：分治法

相关推荐