ArrayList中

Question

找到最接近的元素我有一個排序的數組。給定一個鍵值（不一定在表中），我想找到表中接近鍵值的元素。

我曾考慮使用二進制搜索，但我需要返回最接近的元素，如果該鍵不在表（未-1）。我應該怎麼做？

如果沒有匹配返回-1。這是我目前嘗試使用二進制搜索：

public static long binarySearch (ArrayList<Long> arr, int first, int last, long key) 
{ 

    if (first > last) return -1; 
    int mid = first + (last - first)/2; 
    if (arr.get(mid) == key) 
     return mid; 
    else if (arr.get(mid) > key) 
     return binarySearch(arr, first, mid - 1, key); 
    else 
     return binarySearch(arr, mid + 1, last, key); 
} 

Answer 1

當中間位置元素不等於鍵，你可以計算三角洲ABS（關鍵arr.get（MID）），並檢查它是否是最低的而不是實際的增量（最低的增量，你得到的最接近的值）。最後，如果您沒有在數組中找到關鍵字，則返回delta而不是-1。

注意，你不能初始化增量爲0，因爲以後的任何計算的增量將大於0

Answer 2

變化：

if (first > last) return -1;

到

if (first > last) { 
    // if either first or last is negative, return the first element. 
    // if either first or last are greater than arr length, return the last element. 

    // otherwise, get values in the array for indecies first and last, compare then to 
    // your key and return the closest. 

} 

Answer 3

嘗試像（未經測試）：

public static Long getClosest(List<Long> sortedList, Long key) { 
    int index = Collections.binarySearch(sortedList, key); 
    Long closest; 
    if (index >= 0) { 
     closest = sortedList.get(index); 
    } else { 
     index = -index - 1; 
     if (index == 0){ 
      closest = sortedList.get(index); 
     } else if (index == sortedList.size()){ 
      closest = sortedList.get(index - 1); 
     } else { 
      Long prev = sortedList.get(index - 1); 
      Long next = sortedList.get(index); 
      closest = ((key - prev) < (next - key)) ? prev : next; 
     } 
    } 
    return closest; 
} 

至於說，這個代碼是未經測試，你可能要檢查它是否返回所有角落的情況下正確的值。

Answer 4

這將解決問題，找到最接近的值，找到列表中接近索引的總和，例如{1,4,6,7,8,19}和關鍵字3.二分查找將與圖1和4的最終子集，

如果（1 + 4> 3 + 3）？返回1，否則返回4

if (first > last) 
    { 
     // This makes an Invalid case 
     return -1; 
    } 
    if (first == last) 
    { 
     // then get the valueOf(firstIndex) 
     return arr.get(first-1); 
    } 
    if (first + 1 == last) 
    { 
     // gets value from the first Index 
     int fistKey = arr.get(first-1); 
     // gets value from first Index + 1 i.e next Index 
     int nextKey = arr.get(first); 
     // if valueof(firstIndex) + valueOf(nextIndex) > key then, 
     // key will be closer to valueOf(firstIndex) 
     // else key will be closer to valueOf(nextIndex) 
     return ((fistKey + nextKey) > (key + key)) ? fistKey : nextKey; 
    } 
    else 
    { 
     // assuming List will start its index from 0, then "-1" used for mid calculation 
     int mid = (last+1)/2; 
     int keyFromList = arr.get(mid-1); 
     if (keyFromList == key) 
      return key; 
     if (keyFromList > key) 
      return binarySearch(arr, first, mid , key); 
     else 
      return binarySearch(arr, mid, last , key); 
    } 

Answer 5

幸運的是，Java標準庫，包括Arrays.binarySearch如果在一個陣列中不包含它，讓你的元素的「插入點」：

返回：搜索關鍵字的索引，如果它包含在數組中;否則，（ - （插入點）-1）。插入點被定義爲鍵將被插入到數組中的點： 大於該鍵的第一個元素的索引，或者如果數組中的所有 元素都小於指定的鍵，則該索引將被定義爲 。請注意， 這保證返回值將>> 0當且僅當找到 密鑰。

有了，我們可以非常簡明地實現您的要求：

import java.util.Arrays; 

public class ClosestValue 
{ 
    static long closestValue(long[] sorted, long key) 
    { 
     if(sorted.length==1) {return sorted[0];} // trivial case 
     if(key<sorted[0]) {return sorted[0];} // lower boundary 
     if(key>sorted[sorted.length-1]) {return sorted[sorted.length-1];} // upper boundary 
     int pos = Arrays.binarySearch(sorted, key); 
     if(pos>=0) {return sorted[pos];} // we found an exact match 
     // we didn't find an exact match, now we have two candidates: insertion point and insertion point-1 (we excluded the trivial case before) 
     // pos = -ip-1 | +ip -pos => ip = -pos-1 
     int ip = -pos-1; 
     long closest; 
     if(sorted[ip]-key<key-sorted[ip-1]) {closest=sorted[ip];} // < can be <= if smaller value is preferred 
     else       {closest=sorted[ip-1];} 
     return closest; 
    } 

    public static void main(String[] args) 
    { 
     System.out.println(closestValue(new long[] {1,4,6,7,8,19},3)); 
     System.out.println(closestValue(new long[] {1,2,4,5},3)); 
     System.out.println(closestValue(new long[] {1,2,4,5},7)); 
     System.out.println(closestValue(new long[] {1,2,4,5},-5)); 
    } 
}