419-分治算法思想

「爱情、让人受尽委屈。」 2022-09-05 01:57 184阅读 0赞

## 分治算法思想 ##

![在这里插入图片描述][f222d28b0eb74958b1eef69b60d6a2e9.png]  
**划分的子问题要大于等于2**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
**原问题的解是通过好几个子问题的解合并而来的。如果这个解对于原问题是属于最优解，那么它的解对于子问题的解来说是最优解。最优子结构！**

## 二分搜索 ##

**我们对一组有序的序列采用的是二分搜索算法**  
![在这里插入图片描述][9a01caba1847415b8e50815a87087eba.png]  
**先和中间的元素58比较，和58比较之后，划分子问题，以此类推。**  
比58大的在右边，比58小的在左边，然后每一个区间的左右下标相加除以2，**以此类推，不断划分下去**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]  
**分治算法：原问题的解是无法求出的，需要划分子问题，子问题小到解是已知的，再向上回溯，得到原问题的解。**  
![在这里插入图片描述][33e3f093ee0242fd9ac3948e7c638093.png]  
**子问题的求解方式和原问题一样！！！**  
**划分的子问题没有重复计算！！！**

//分治算法思想 - 二分搜索
    bool binarySearch(vector<int>& vec, int i, int j, int val) {
        
    	if (i > j) {
        //元素不存在
    		return false;
    	}
    
    	int mid = (i + j) / 2;
    	if (vec[mid] == val) {
        //子问题[i,j] 解是已知的了
    		return true;
    	}
    	else if (vec[mid] > val) {
        //在[i, mid-1]子规模问题中
    		return binarySearch(vec, i, mid - 1, val);
    	}
    	else {
        //在[mid+1, j]子规模问题中
    		return binarySearch(vec, mid + 1, j, val);
    	}
    }
    int main()
    {
        
    	vector<int> vec;
    	for (int i = 0; i < 11; ++i) {
        
    		vec.push_back(rand() % 100);
    	}
    	sort(vec.begin(), vec.end());
    	for (int v : vec) {
        
    		cout << v << " ";
    	}
    	cout << endl;
    
    	bool result = binarySearch(vec, 0, vec.size() - 1, 34);
    	cout << "result:" << result << endl;
    
    	return 0;
    }

[f222d28b0eb74958b1eef69b60d6a2e9.png]: /images/20220829/9f8d1c13609f4ff2b3a2de8a62e34a05.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/09667a41855a47fc841ff9be938ff80d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/d26867d4b1a246ce8b2ed3a77e2399b9.png
[9a01caba1847415b8e50815a87087eba.png]: /images/20220829/01fb3ea02e80414fbe0bfe1f34548796.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/a6c6a6a82b3646acb02c8e3833df642f.png
[33e3f093ee0242fd9ac3948e7c638093.png]: /images/20220829/44fc18350ef64f69b70fcc2d7f5ee318.png