分治法查找k1到k2大的数

Question

以下代码用来求一个数组中k1大到k2-大的数-要求数组不能进行完全排序-下面的快排我验证过了没问题-就是后面那个findkk函数-不知道为什么运行到一半的时候就会自动退出，求大神帮忙看看问题出在哪QAQ

 #include<iostream>
using namespace std;

void sweap(int &arr1,int &arr2 ){
    int temp = arr1;
    arr1 = arr2;
    arr2 = temp;
}

int Quick(int arr[], int i, int j){
    int mark = i;
    i++;
    while (i < j){
        while (arr[i] < arr[mark] && i < j){
            i++;
        }
        //cout << endl<<"暂停时为i第"<<i+1<<"位，该数为：" << arr[i];
        //cout <<endl<< "j开始向下移动：";
        while (arr[j] > arr[mark] && j >= i)
        {
            //cout << arr[j] << "  ";
            j--;
        }
        //cout << endl << "暂停时j为第" <<j+1<< "位，该数为：" << arr[j];
        //cout << "交换两数" << arr[i] << "  " << arr[j];
        sweap(arr[i], arr[j]);
    }
    sweap(arr[i], arr[j]);
    //cout << endl << "最终交换的两数为" << arr[mark] << "  " << arr[j];
    sweap(arr[mark], arr[j]);
    return j;
}

void findkk(int arr[], int start, int end, int k1, int k2,bool fk1,bool fk2){
    if (fk1 && fk2){

        return;
    }

    if (start < end){
        int s;
        s = Quick(arr, start, end);
        if (s + 1 == k1){
            fk1 = true;
            findkk(arr, s + 1, end, k1, k2, fk1, fk2);
            //cout << endl << s << "  " << end;
        }
        else if (s + 1 == k2){
            fk2 = true;
            findkk(arr, start, s - 1, k1, k2, fk1, fk2);
            //cout << endl << start << "  " << s-1;
        }
        else if (s < k1)
        {
            findkk(arr, s + 1, end, k1, k2, fk1, fk2);
            //cout << endl << s << "  " << end;
        }
        else if (s > k1 &&s < k2){
            findkk(arr, start, s-1, k1, k2, fk1, fk2);
            //cout << endl << start << "  " << s-1;
            findkk(arr, s + 1, end, k1, k2, fk1, fk2);
            //cout << endl << s+1 << "  " << end;
        }
        else if (s > k2)
        {
            findkk(arr, start, s - 1, k1, k2, fk1, fk2);
            //cout << endl << start << "  " << s-1;
        }
    }
    else if (start == end){
        if (start == k1){
            fk1 = true;
            findkk(arr, start, end, k1, k2, fk1, fk2);
        }
        else if (start == k2){
            fk2 = true;
            findkk(arr, start, end, k1, k2, fk1, fk2);
        }
        else{
            cout << "有问题的退出！";
            return;
        }


    }
    else if (start > end){
        cout << "error!";
        //return;
    }


}

int main(){
    int n = 8;
    int k1 = 2, k2 = 4;
    bool fk1 = false, fk2 = false;
    int* arr = new int[n];
    cout << "请输入8个无序数：";
    for (int i = 0; i < n; i++){
        cin >> arr[i];
    }

    cout << "请输入k1 k2：";
    cin >> k1 >> k2;
    //cout<<endl<<Quick(arr, 0, n - 1);
    findkk(arr, 0, n - 1, k1, k2, fk1, fk2);
    for (int i = k1 - 1; i < k2; i++){
        cout << arr[i] << "  ";
    }
    return 0;
}

Answer 1

分治法的基本思想是将一个规模为n的问题分级为k个规模较小的子问题，这些子问题互相独立，且与原问题相同。递归的解这些子问题，然后将各子问题的解合并得到原问题的解，二分查找是分治策略的一个典型例子，分置策略的典型例子还有就是合并排序（在排序算法里有合并排序的c语言描述），下面给出二分查找的代码：

#include

int main()

{

int a[10],i;

int binarysearch(int a[],int n,int x);

for(i=0;i<10;i++)

scanf("%d",&a[i]);

printf("%d/n",binarysearch(a,10,3));//找a数组中的数字3的位置

return 0; 

}

int binarysearch(int a[],int n,int x)

{

int left=0,right=n-1,middle;

while(left<right)

{

                 middle=(left+right)/2;

                 if(x==a[middle])return(middle);

                 else if(x>a[middle])left=middle+1;

                 else right=middle-1;

}

}