c++ - 查找未排序数组的 K 元素，就像它已排序一样 - 分而治之

Question

我有一个关于使用分而治之算法实现的问题。

因此，我们有一个未排序的数组 V[]，我们必须找到数组的第 k 个元素，就像数组已排序但不对数组 v 完全排序一样。

例子：

数组大小 = 8; k = 3; 例如，如果 k = 3 且 v = {2, 7, 5, 9, 8, 10, 3, 4}，则该数组的 k 元素为 5。

Obs：数组的索引从 0 到 size - 1。

我的代码：

void read_STL(std::vector<int>& vect,int &k)
{
   std::ifstream fisier("file.txt");
   int dim;
   fisier >> dim;
   fisier >> k;
   for (int i = 0; i < dim; i++)
   {
      int elem;
      fisier >> elem;
      vect.push_back(elem);
   }
   fisier.close();
}

bool criteriu(int i, int j)
{
   return (i < j);
}

int search_DQ(std::vector<int>& vect, int st, int dr,int k)
{
   if (st == dr) 
   {
      return vect[st];
   }
   int mijl = (st + dr) / 2;
   if (k == mijl) 
   {
      return vect[k];
   }
   else if (k < mijl) 
   {
      return search_DI(vect, st, mijl - 1, k);
   }
   else 
   {
      return search_DQ(vect, mijl + 1, dr, k);
   }
}

int main()
{
   std::vector<int>vect;
   int st, dr, k;
   read_STL(vect,k);
   st = 0;  dr = vect.size() - 1;
   std::cout<<search_DQ(vect, st, dr,k);
   return 0;
}

标签： c++