Làm cách nào để tìm phần tử mảng gần nhất với số tùy ý (không phải thành viên)?

Question

Câu hỏi dường như tương tự: "Finding closest number in an array" (bằng Java) và "find nearest match to array of doubles" (thực sự là vấn đề địa lý).

Tôi có một (sắp xếp) mảng đôi. Với một số tùy ý (có thể hoặc có thể không khớp chính xác với một trong các phần tử mảng), làm thế nào tôi có thể trả về chỉ số của số gần nhất?

Ví dụ, sử dụng các mảng sau:

• 1,8
• 2,4
• 2,7
• 3,1
• 4,5

Truy vấn 2.5 sẽ trở lại với một chỉ số của 1 , tương ứng với giá trị 2.4.

Điểm thưởng để phát hiện các giá trị nằm hoàn toàn bên ngoài phạm vi của các phần tử mảng. Ví dụ, bằng cách sử dụng mảng được liệt kê ở trên, mã của bạn có thể quyết định rằng 4.6 là trong, nhưng 5.9 là ra ngoài. Nếu bạn muốn thử phần này của câu hỏi, các chi tiết cụ thể nằm trong tay bạn.

Answer 1

Array.BinarySearch, mà trả về:

Chỉ số giá trị quy định trong mảng chỉ định, nếu giá trị được tìm thấy. Nếu giá trị không được tìm thấy và giá trị nhỏ hơn một hoặc nhiều phần tử trong mảng, một số âm là phần bổ sung bit của chỉ mục của phần tử đầu tiên lớn hơn giá trị. Nếu không tìm thấy giá trị và giá trị lớn hơn bất kỳ phần tử nào trong mảng, một số âm là số bổ sung bit của (chỉ mục của phần tử cuối cùng cộng với 1).

Bây giờ, bạn sẽ không nhận được 100% số tiền đó, vì bạn sẽ biết số đó nhỏ hơn hoặc lớn hơn so khớp, nhưng nó thực sự chỉ để lại hai chỉ số để kiểm tra.

Answer 2

Something như thế này:

double[] values = new double[] 
{ 
    1.8, 
    2.4, 
    2.7, 
    3.1, 
    4.5 
}; 

double difference = double.PositiveInfinity; 
int index = -1; 

double input = 2.5; 

for (int i = 0; i < values.Length; i++) 
{ 
    double currentDifference = Math.Abs(values[i] - input); 

    if (currentDifference < difference) 
    { 
     difference = currentDifference; 
     index = i; 
    } 

    // Stop searching when we've encountered a value larger 
    // than the inpt because the values array is sorted. 
    if (values[i] > input) 
     break; 
} 

Console.WriteLine("Found index: {0} value {1}", index, values[index]); 

Answer 3

Một cách để làm điều này bằng cách dùng LINQ là như thế này:

public int GetClosestIndex(List<double> doublelist, double targetvalue) 
{ 
    return doublelist.IndexOf(doublelist.OrderBy(d => Math.Abs(d - targetvalue)).ElementAt(0)); 
} 

Nó có thể có một số vấn đề hiệu suất, nhưng Nếu danh sách không phải là dài, nó không nên đặt ra một vấn đề. Ngoài ra, nếu hai phần tử đều cách xa giá trị đích, nó sẽ trả về chỉ mục đầu tiên của các phần tử đó.

Answer 4

Có lẽ không phải là giải pháp nhanh nhất, nhưng chắc chắn thú vị eye-candy:

double search; 
double[] array; 

var nearest = (
    from value in array 
    orderby Math.Abs(value - search) 
    select value).First(); 

var index = array.IndexOf(nearest); 

Lưu ý rằng điều này sẽ hoàn toàn chậm hơn so với một tìm kiếm nhị phân, bởi vì nó cần để xử lý mỗi phần tử trong mảng và phương tiện sắp xếp xây dựng bảng băm của các mục đó.

Answer 5

List<int> results; 
int target = 0; 
int nearestValue = 0; 
if (results.Any(ab => ab == target)) { 
    nearestValue= results.FirstOrDefault<int>(i => i == target); 
} else { 
    int greaterThanTarget = 0; 
    int lessThanTarget = 0; 
    if (results.Any(ab => ab > target) { 
     greaterThanTarget = results.Where<int>(i => i > target).Min(); 
    } 

    if (results.Any(ab => ab < target)) { 
     lessThanTarget = results.Where<int>(i => i < target).Max(); 
    } 

    if (lessThanTarget == 0) { 
     nearestValue= greaterThanTarget; 
    } else if (greaterThanTarget == 0) { 
     nearestValue = lessThanTarget; 
    } else { 
     if (target - lessThanTarget < greaterThanTarget - target) { 
      nearestValue = lessThanTarget; 
     } else { 
      nearestValue = greaterThanTarget; 
     } 
    } 
}