如何将整数数组降序排序且最大值在索引0，同时保留二分查找功能？

核心问题分析 #

你目前的代码是先升序排序数组，再倒序输出，数组实际存储还是升序（最大值在索引19），只是显示成降序。同时二分查找函数是为升序数组设计的，直接改数组顺序会导致查找逻辑失效，需要同步调整二分查找的判断逻辑。

分步修复 #

1. 实现真正的降序数组存储

替换默认的升序排序，使用greater<int>()指定降序排序，同时修正n变量的重复定义问题（多次定义int n会导致变量覆盖，无法正确记录实际读取的元素数量）：

• 读取文件时，用全局的n记录实际读取的元素个数，不要在循环里重新定义int n
• 排序时使用实际读取的元素数，而非固定20（避免处理未初始化的0值）

2. 调整二分查找适配降序数组

原二分查找是针对升序数组的逻辑，降序数组的判断逻辑需要反转：

• 当array1[mid] > num：目标值在mid的右侧（降序数组右边元素更小），搜索范围改为mid+1到r
• 当array1[mid] < num：目标值在mid的左侧（降序数组左边元素更大），搜索范围改为p到mid-1

修改后的完整代码 #

#include <iostream>
#include <fstream>
#include <algorithm> // 必须包含头文件才能使用sort和greater

using namespace std;

int binarySearch(int array1[], int p, int r, int num) {
    if (p <= r) {
        int mid = p + (r - p) / 2; // 替换(p+r)/2，避免整数溢出
        if (array1[mid] == num)
            return mid;
        // 降序数组的查找逻辑：和升序完全反转
        if (array1[mid] > num)
            return binarySearch(array1, mid + 1, r, num);
        if (array1[mid] < num)
            return binarySearch(array1, p, mid - 1, num);
    }
    return -1;
}

int main() {
    int array1[20]{};
    ifstream inputData("input.txt");
    int n = 0; // 用这个变量记录实际读取的元素个数
    int num;

    if (!inputData) {
        cout << "Cannot open file.\n";
        return 0;
    }

    cout << "The unsorted list of integers:\n";
    // 循环里不要再重新定义int n，用全局的n计数
    while (n < 20 && inputData >> array1[n]) {
        cout << array1[n] << " ";
        n++;
    }
    cout << "\n\nThe sorted list of integers in descending order:\n";

    // 按实际读取的元素数n进行降序排序
    sort(array1, array1 + n, greater<int>());
    // 正序输出数组，此时最大值在索引0
    for (int i = 0; i < n; i++)
        cout << array1[i] << " ";

    cout << "\n\nEnter an integer to search: ";
    cin >> num;
    // 查找范围是0到n-1，对应实际存储的有效元素
    int index = binarySearch(array1, 0, n - 1, num);
    if (index == -1) {
        cout << num << " could not be found. Please restart the program and try another number.";
    } else {
        cout << "Integer " << num << " found at index [" << index << "] in the sorted integer array.";
    }

    return 0;
}

关键修改说明 #

• 排序逻辑：sort(array1, array1 + n, greater<int>())直接将数组按降序排列，此时最大值在索引0，数组存储顺序和显示顺序一致
• 二分查找逻辑：完全反转升序的判断条件，确保在降序数组中能正确缩小查找范围
• 变量修正：统一用n记录实际读取的元素数，避免未初始化的0值干扰排序和查找
• 溢出优化：将mid = (p + r)/2改为mid = p + (r - p)/2，防止p+r超出int范围导致溢出

内容的提问来源于stack exchange，提问作者JadronAU