查找數組中的最小索引，使某個鍵小於或等於數組[索引]

Question

我試圖改變二分查找有點，所以而不是隻找到一個元素的索引當且僅當它是在數組中，我想查找最小索引，使得Array [index]> = key。所以如果我有一個像int A[5] = {1,5,10,15,20}這樣的數組，我叫search(A, 12, 5)（其中5只是數組的長度），它將返回=> 3，因爲A[3] = 15 >= 12。如果我搜索20以上的東西，它會給我5回或其他任意數字。

我試圖儘可能接近傳統二進制搜索。任何幫助？

（這裏是傳統的二進制搜索）

int binarysearch(int A[], int key, int length) { 
    int low = 0; 
    int high = length - 1; 
    while (low <= high) { 
     int mid = (low + high)/2; 
     if (key < A[mid]) { 
      high = mid - 1; 
     } else if (key > A[mid]) { 
      low = mid + 1; 
     } else { 
      return mid; 
     } 
    } 
    return -1; 
} 

Answer 1

我認爲這樣做會增加一個檢查時，關鍵是小於中進入這會看看前一個條目的最佳方式。如果關鍵字大於那個條目，我們有我們的答案（因爲如果你在列表中放下一個，條目不會大於關鍵字）。因此，代碼將是這個樣子：

int low = 0; 
int high = length - 1; 
while (low <= high) 
{ 
    int mid = (low + high)/2; 
    if (key < A[mid]) 
    { 
     if (key > A[mid-1] 
     { 
      return mid 
     } 
     high = mid - 1; 
    } 
    else if (key > A[mid]) 
    { 
     low = mid + 1; 
    } 
    else 
    { 
    return mid; 
    } 
} 
return -1; 

這將需要更復雜的，如果你的列表允許重複，但它原本應該工作。

Answer 2

而不是return -1，只是返回mid