如果我有一個排序的陣列arr[]conatains neleemnts，我怎么能找到一定數量的出現的次數key與O（LOGN）的復雜性？
例如：對于
int arr[] = {0, 1, 2, 2, 6, 6, 6, 7};
int n = 8;
int key = 6;
int first, last;
我會得到3。
我解決這個問題的方法是進行兩次二進制搜索，一次搜索第一次出現的索引key，將結果保存在int first. 另一個搜索最后一次出現的索引key，將結果保存在last. 那么剩下要做的就是回傳
last - first 1。
但是當我開始撰寫問題時，我遇到了一個問題，我無法計算last導致奇怪結果的原因。我一直在嘗試除錯我的代碼，但沒有成功，有什么建議嗎？
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
int ex2(int*, int, int);
int main()
{
int arr[] = {1, 4, 6, 6, 6, 7, 7, 8, 11, 14, 22};
printf("%d", ex2(arr, 11, 6));
return 0;
}
int ex2(int* a, int n, int x)
{
int low = 0, high = n - 1, mid, first = 0, last = 0;
// bin first
while (low <= high)
{
mid = (low high) / 2;
if (a[mid] == x)
{
if (mid - 1 < low || a[mid - 1] < x)
{
first = mid;
break;
}
else
high = mid - 1;
}
if (a[mid] < x)
low = mid 1;
else
high = mid - 1;
}
// bin last
low = 0;
high = n - 1;
while (low <= high)
{
mid = (low high) / 2;
if (a[mid] == x)
{
if (mid 1 > high|| a[mid 1] > x)
{
last = mid;
break;
}
else
low = mid 1;
}
if (a[mid] < x)
low = mid 1;
else
high = mid - 1;
}
return last - first 1;
}
當我運行它時：
int arr[] = {1, 4, 6, 6, 6, 7, 7, 8, 11, 14, 22};
printf("%d", ex2(arr, 11, 6));
我得到-1（因為last它仍然0不同于first保持正確值2- > 0 - 2 1 = -1）。當我得到 3 時（6 出現 3 次）。
uj5u.com熱心網友回復：
更改if (a[mid] < x)到else if (a[mid] < x)它出現這兩個地方。
否則，在a[mid] == x你設定low（在第一次搜索中）或high（在第二次搜索中）的情況下，代碼將通過這個測驗a[mid] < x并錯誤地設定另一個邊界。插入else排除了這一點。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/407553.html
標籤：