C++ - 使用关联数组，按值排序后无法按键搜索

Question

在下面的代码中，我有一个关联数组，其中包含作为键的字母表中的字母以及与它们关联的任意值。我已经实现了一个快速排序功能来根据值降序对它们进行排序。我有一个二进制搜索功能来搜索特定的键(字母)。二进制搜索在我排序之前工作正常，但在我排序之后，使用它只能找到一些字母。尝试自己完成它，我在执行 quickSort() 之前和之后遍历数组，它似乎确认这些值仍然存在，尽管它们已排序。我做错了什么？

#include <iostream>
#include <array>

using namespace std;

int binarySearch(int arr[][2], int value, int left, int right)
{
    while (left <= right)
    {
        int middle = (left + right) / 2;
        if (arr[middle][0] == value)
            return middle;
        else if (arr[middle][0] > value)
            right = middle - 1;
        else
            left = middle + 1;
    }
    return -1;
}

void quickSort(int arr[][2], int left, int right)
{
    int i = left, j = right;
    int tmp1, tmp2;
    int pivot = arr[(left + right) / 2][1];

    /* partition */
    while (i <= j)
    {
        while (arr[i][1] > pivot)
            i++;
        while (arr[j][1] < pivot)
            j--;
        if (i <= j)
        {
            tmp1 = arr[i][0];
            tmp2 = arr[i][1];

            arr[i][0] = arr[j][0];
            arr[i][1] = arr[j][1];

            arr[j][0] = tmp1;
            arr[j][1] = tmp2;

            i++;

            j--;
        }
    };

    /* recursion */
    if (left < j)
        quickSort(arr, left, j);
    if (i < right)
        quickSort(arr, i, right);

}

int main()
{
    const int alphLength = 26;
    int assocArr[alphLength][2] = { {'A', 5},  {'B', 2}, {'C', 4}, {'D', 3},  {'E', 1}, {'F', 0}, {'G', 0}, {'H', 0}, {'I', 0},
        {'J', 0}, {'K', 0}, {'L', 0}, {'M', 0}, {'N', 0}, {'O', 0}, {'P', 75}, {'Q', 0}, {'R', 0},
        {'S', 0}, {'T', 0}, {'U', 0}, {'V', 0}, {'W', 0}, {'X', 50}, {'Y', 0}, {'Z', 100} };

char a;
char searchLetter = 'Z';

for (int i = 0; i < alphLength; i++)
{
    a = assocArr[i][0];
    cout << "index " << i << ": " << a << endl;
}

cout << "found " << searchLetter << " before quickSort() at " << binarySearch(assocArr, searchLetter, 0, alphLength-1) << endl;

quickSort(assocArr, 0, alphLength-1);

for (int i = 0; i < alphLength; i++)
{
    a = assocArr[i][0];
    cout << "index " << i << ": " << a << endl;
}

cout << "found " << searchLetter << " after quickSort() at " << binarySearch(assocArr, searchLetter, 0, alphLength-1) << endl;

}

Answer 1

二分搜索仅适用于排序数组，它们需要按照您在搜索中用于比较它们的相同标准进行排序。您的数组开始时按字母升序排序，而您的二进制搜索按字母升序搜索，因此可以正常工作。然后按值排序，这会打乱字母。然后您再次按字母升序进行二分查找，这将不起作用，因为数组不再按字母升序排序。