在排序數組中找到小於x的最大值

Question

假設我有一個整數排序陣列int[]，並且我想搜索與某個輸入數最接近的較小值。

例如，如果該數組包含（1），（23），（57），（59），（120）且輸入是109輸出應爲59

我只是想看到建議，並與我已有的方法進行比較。

Answer 1

使用Array.BinarySearch。如果輸入在列表中，它將返回索引，如果不是，那麼它將返回第一個較大值的索引的補碼。您只需倒置結果並減去一個即可得到最接近的較小值的索引。

int[] arr = { 1, 23, 57, 59, 120 }; 
int index = Array.BinarySearch(arr, 109); 
if (index < 0) 
{ 
    index = ~index - 1; 
} 
if (index >= 0) 
{ 
    var result = arr[index]; 
} 

請注意，如果您有一個小於最小元素的輸入，那麼您沒有明確定義的答案。

Answer 2

使用LINQ：

int[] arr = new[] { 1, 23, 57, 59, 120 }; 
int target = 109; 
int max = arr.Where(n => n < target).Max(); 

也許不是最快的，但可能是最容易實現的。也不依賴於數組被排序，因爲二進制搜索。

請注意，如果Where篩選器不包含任何元素，則調用Max會引發異常，因此您可能需要檢查是否有可能。

Answer 3

我會去一個LINQ溶液（更新：補充一點更多的代碼從被類似恐懼的同類解決方案停止）：

int[] arr1 = { 1, 23, 57, 59, 120 }; 
int maxResult; 
string errorMsg; 
try 
{ 
    maxResult = arr1.Where(x => x <= 109).Max(); 
} 
catch(Exception e) 
{ 
    errorMsg = e.Message; 
    // do some error stuff here :) 
    return null; 
} 
// party on your maxResult... 

Answer 4

只是推斷在其他LINQ解決方案，這擴展方法將返回-1，如果沒有對象符合過濾器，並希望該列表是所有的正整數

public static int SearchForLimit(this IEnuemerable<int> sequence, Predicate<int> filter) 
{ 
    return (from i in sequence 
      let n = filter(i) ? i : -1 
      select n).Max() 
} 

用法是這樣的：

int[] arr1 = { 1, 23, 57, 59, 120 }; 
int limitedBy109 = arr1.SearchForLimit(i => i < 109); 

Answer 5

int getIndex(long[] list, long value) 
{ 
    int top = 0; 
    int bot = list.length-1; 
    int mid=0; 
    while (top <= bot) 
    { 
     mid = (top+bot)/2; // NB integer arithmetic 
     if (value < list[mid]) 
     { 
      if (mid == 0) 
       // value < than first item 
       return -1; 
      else 
       bot = mid-1; 
     } 
     else // value >= list[mid] 
     { 
      if (mid == list.length-1) 
       // value is >= last item 
       break; 
      else if (value >= list[mid+1]) 
       top = mid+1; 
      else // list[mid] must be biggest <= value 
       break; 
     } 
    } 
    return mid; 
}