Sıralı bir dizideki x'den küçük en büyük değeri bul

Question

Diyelim ki, sıralanmış bir tamsayılar dizisi var int[] ve en küçük değeri en düşük bir giriş numarasına aramak istiyorum. Dizi içeriyorsa

örneğin (1), (23), (57), (59), (120) ve giriş 109, çıkış sadece çalışıyorum 59.

olmalıdır önerileri görmek ve sahip olduğum yaklaşımlarla karşılaştırmak.

Answer 1

Array.BinarySearch'u kullanın. Giriş listede bulunuyorsa, indeksi döndürür ve eğer değilse, ilk büyük değerin dizinini tamamlar. Sonucu en küçük değerin indeksini elde etmek için sonucu tersine çevirip çıkar.

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]; 
} 

En küçük öğeden daha küçük bir girişiniz varsa, iyi tanımlanmış bir yanıtınız olmadığını unutmayın. Linq kullanarak

Answer 2

:

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

Belki değil en hızlı ama uygulamak için muhtemelen en kolay. Ayrıca, ikili aramada olduğu gibi sıralanan diziye de güvenmez.

Max numaralı aramanın, Where filtresinin hiçbir öğeyle sonuçlanmadığı durumlarda bir istisna atacağını unutmayın; bu nedenle, bir olasılık olup olmadığını kontrol etmek isteyebilirsiniz.

Answer 3

I ( updated : korku benzer çözümüne benzer olmaktan durdurmak için biraz daha kod eklemek): Bir linq çözümü için gitmek istiyorum

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

sadece diğer LINQ çözümlerine tahmin etmek bu uzatma yöntemi dönecektir -1 hiçbir nesne filtresi uyar ve liste

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() 
} 

kullanım şu şekilde görünecektir tüm pozitif tam olduğunu bekliyorsa:

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