看看二分查找代码错误

Question

不知道错哪里
我的测试数据：

输入

3
5 1 4

输出

错误（就是我的）
1 5 4

正确
1 4 5

代码：

#include<iostream>
#include<cstdio>
using namespace std;
void L_Swap(int &a,int &b)
{
    /*交换ab值*/
    int S=a;
    a=b;
    b=S;  //交换 
}
void L_Sort(int a[],int Begin,int End)
{
    /*二分查找函数*/ 
    if(Begin>=End)  //如果没有排序对象，跳过 
    {
        return;
    }
    else  //否则排序 
    {
        int Mid=a[(Begin+End)/2],i=Begin,j=End;  //定义函数 
        while(i<j)
        {
            while(a[i]<Mid && i<j)  //查找左边的违规数 
            {
                i++;
            }
            while(a[j]>Mid && i<j)  //查找右边的违规数 
            {
                j--;
            }
            L_Swap(a[i],a[j]);  //交换两方违规数 
        }
        L_Sort(a,Begin,Mid-1);  //继续进行左侧排序 
        L_Sort(a,Mid+1,End);  //继续进行右侧排序 
    }
}
int a[1001];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    L_Sort(a,0,n-1);
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<' ';
    }
}

Answer 1

答案参考ChatGPT ，如果有参考价值麻烦采纳一下，谢谢啦！！_

在L_Sort函数中计算Mid的表达式错误，应该是Mid=a[(Begin+End)/2]，而不是Mid=a[Begin+End/2]，因为加法优先级高于除法。

在L_Sort函数中，快速排序的分割点应该是Mid，而不是a[(Begin+End)/2]，因为Mid是分割点的值。应该将while循环结束后，Mid和a[j]交换位置，以保证Mid作为分割点的值正确。

在while循环中，第二个while条件应该是a[j]>=Mid，而不是a[j]>Mid，因为当a[j]==Mid时，也应该停止查找。

在L_Sort函数递归调用时，应该将Mid-1和Mid+1传入，而不是Begin和End，因为Mid是分割点，不应该重复排序。

下面是修改后的代码：

```c

#include<iostream>
#include<cstdio>
using namespace std;

void L_Swap(int &a, int &b)
{
    int S = a;
    a = b;
    b = S;
}

void L_Sort(int a[], int Begin, int End)
{
    if(Begin >= End)
    {
        return;
    }
    else
    {
        int Mid = a[(Begin+End)/2];
        int i = Begin, j = End;
        while(i < j)
        {
            while(a[i] < Mid && i < j)
            {
                i++;
            }
            while(a[j] >= Mid && i < j)
            {
                j--;
            }
            L_Swap(a[i], a[j]);
        }
        L_Swap(a[j], a[(Begin+End)/2]);
        L_Sort(a, Begin, j-1);
        L_Sort(a, j+1, End);
    }
}

int a[1001];

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    L_Sort(a, 0, n-1);
    for(int i = 0; i < n; i++)
    {
        cout << a[i] << ' ';
    }
    return 0;
}

```