我撰寫了這個簡碼來在復雜度為O(log n)的排序陣列（從高到低）中查找元素 x 位置。n并arr表示陣列的邊緣。但是，它似乎無法正常作業。有什么建議？
int ex2_1(int *arr, int n, int key)
{
if (n == 0)
return -1;
if (arr[n / 2] == key)
return n / 2;
if (arr[n / 2] > key)
return ex2_1(arr n / 2 1, n - n / 2 - 1, key);
return ex2_1(arr, n / 2, key);
}
因為int arr[] = { 9, 7, 7, 5, 3, 3, 3, 1 };,int n = 8和int key = 3,4我應該得到5.
uj5u.com熱心網友回復：
您的遞回函式回傳錯誤結果的原因是您應該將遞回呼叫的結果偏移從作為遞回呼叫起點的陣列開頭的偏移量。僅當遞回呼叫找到匹配項時才應執行此操作。
這是修改后的版本：
int ex2_1(const int *arr, int n, int key) {
int m = n / 2;
if (n == 0)
return -1;
if (arr[m] == key)
return m;
if (arr[m] > key) {
int res = ex2_1(arr m 1, n - m - 1, key);
return res < 0 ? res : res m 1;
} else {
return ex2_1(arr, m, key);
}
}
uj5u.com熱心網友回復：
在優化 chqrlie 的代碼后，我得到了這個，它運行良好：
int ex2_1(int* arr, int n, int key)
{
if (n == 0) return -1;
if (arr[n/2] == key) return n / 2;
if (arr[n/2] > key)
{
int a = ex2_1(arr n/2 1, n - n/2 - 1, key);
if (a == -1) return -1;
return n / 2 1 a;
}
return ex2_1(arr, n/2, key);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/405878.html
標籤：