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