C++ - 有關聯數組，在按值排序後不能按鍵搜索

在下面的代碼中，我有一個關聯數組，其中包含字母表中的字母作爲鍵以及與它們關聯的任意值。我已經實現了一個快速排序函數來根據值降序對它們進行排序。我有一個二進制搜索功能來搜索特定的鍵（字母）。二進制搜索在我排序之前工作正常，但在排序後，只有一些字母被使用。試圖通過我自己的工作，我執行quickSort（）之前和之後循環數組，似乎確認這些值仍然存在，雖然他們排序。我究竟做錯了什麼？C++ - 有關聯數組，在按值排序後不能按鍵搜索

#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; 

}

來源

2016-05-21 Gerald

二進制搜索僅適用於已排序的數組，它們需要按照您在搜索中用於比較它們的相同條件進行排序。你的數組開始按字母升序排序，而你的二進制搜索按字母升序搜索，所以這個工作。然後，您按價值對其進行排序，從而打亂字母。然後再按升序進行二分搜索，這將不起作用，因爲該數組不再按字母升序排序。

來源

2016-05-21 15:14:42

C++ - 有關聯數組，在按值排序後不能按鍵搜索

回答

相關問題