The C recursive algorithm searches for the number with the largest K in the array

1. Overview

Chinese people always like to talk about seniority. Everyone wants to be the boss, but it can't be done. It's also good to be an old 2, an old 3, and an old K. You must have seen such an argument: Two people quarrel, one is very strong, and the other one can't stand it and says, "Who are you? ", the following through this article is to solve the problem of finding out who!

2. Application scenarios

Find out the value of the K-th large element in the vector V [first, last]

3. Analysis

If the vector V is ordered by sorting algorithm, Then the K element is the element indexed v. length-k. This will solve the problem, But the efficiency is not high, Because this is equivalent to using the strength of our whole army to annihilate one enemy team, The loss outweighs the gain. Think back to the sub-table in quick sorting, and divide the target vector into two sub-tables every time. The left sub-table is all smaller than the middle element v [mid], and the right sub-table is larger than the middle element v [mid], which can reduce the search scope, because I can find the target element only by looking up the left sub-table or the right sub-table. As shown in the following figure, we can divide the vector v into the following

Left(<=KLargest)

KLargest

Right(>=KLargest)

According to this train of thought, We still use the table splitting strategy in quick sorting, Firstly, the vector V is separated from the middle position and divided into left and right. After separation, if the index of the middle value is exactly equal to K, it will be found. Otherwise, if the index of the middle element is greater than K, it will continue to search in the left sub-table, ignoring the right sub-table. If the index of the middle value is less than K, it will continue to search in the right sub-table, and so on.

The sub-table partition function in Quick Sort is:

/// <summary>
///  Switch position 
/// </summary>
/// <param name="v"></param>
/// <param name="index1"></param>
/// <param name="index2"></param>
private void Swrap(int[] v, int index1, int index2)
{
  int temp = v[index1];
  v[index1] = v[index2];
  v[index2] = temp;
}
/// <summary>
///  Will the vector V Index in {first,last) Divided into two left and right sub-tables 
/// </summary>
/// <param name="v"> Vector V</param>
/// <param name="first"> Start position </param>
/// <param name="last"> End position </param>
private int PivotIndex(int[] v, int first, int last)
{
  if (last == first)
  {
    return last;
  }
  if (last - first == 1)
  {
    return first;
  }
  int mid = (first + last) / 2;
  int midVal = v[mid];
  // Exchange v[first] And v[mid]
  Swrap(v, first, mid);
  int scanA = first + 1;
  int scanB = last - 1;
  for (; ; )
  {

    while (scanA <= scanB && v[scanA] < midVal)
    {
      scanA++;
    }
    while (scanB > first && midVal <= v[scanB])
    {
      scanB--;
    }
    if (scanA >= scanB)
    {
      break;
    }
    Swrap(v, scanA, scanB);
    scanA++;
    scanB--;
  }
  Swrap(v, first, scanB);
  return scanB;

}

Design a function, FindKLargest (int [] v, int first, int last, int k); This function includes four parameters: the vector V, the starting position first, the ending position last, and K in the k, then the function is:

After calling FindKLargest, because the array is sorted from small to large, the value of the large element of K is V [v. Length-k];

void FindKLargest(int[] v, int first, int last, int k)
{

  // Represents the index of the value in the sub-table 
  int index = 0;
  index = PivotIndex(v, first, last);
  if (index == k)
  {
    // Found it K Big 
    return;
  }

  if (index > k)
  {
    // Find only in the left subtable 
    FindKLargest(v, first, index, k);
  }

  else
  {
    // Find only in the right child table 
    FindKLargest(v, index, last, k);
  }
}

4. Running results:

Original vector: v = {100, 200, 50, 23, 300, 560, 789, 456, 123, 258}
first = 0; last = v. Length; k=3
Output: 456

5. Conclusion

Using recursive algorithm, more complex problems can be divided into smaller and smaller problems, This can simplify complex problems, and this idea also plays a vital role in system design and architecture. A good architect, facing complex problems, can turn decay into magic, while bad ones often backfire. Their specialty is that simple problems are complicated.

6. Project documents
http://xiazai.ofstack.com/201606/yuanma/FindK(ofstack.com).rar