需要幫助設計分割和征服算法的僞代碼

Question

給定一個存儲n個整數的有序數組A和一個值鍵。設計 高效的分而治之算法返回值 關鍵的指標，如果它可以在陣列A.Otherwise發現，該算法返回0

Answer 1

我覺得你的描述，最好的選擇是二進制搜索（二分搜索）。算法是將數組分成兩半，如果在中間找到的元素高於，低於或等於您正在查找的物品，則購買。這是爲了減少搜索空間以對數查找元素或確定元素不在矢量中。數組必須是有序的。

這是C++的一個例子

#include <vector> 



bool busqueda_dicotomica(const vector<int> &v, int principio, int fin, int &x){ 
    bool res; 
    if(principio <= fin){ 
     int m = ((fin - principio)/2) + principio; 
     if(x < v[m]) res = busqueda_dicotomica(v, principio, m-1, x); 
     else if(x > v[m]) res = busqueda_dicotomica(v, m+1, fin, x); 
     else res = true; 
    }else res = false; 
    return res; 
} 

我覺得你的算法不應該返回0，如果沒有找到，因爲如果你想返回元素的索引，0是第一個元素的索引

In this article is the detailed explanation of the binary search或in this other