CODEWITHSUNDEEP
javabinary-search
user3090011
user3090011

Reputation: 31

find closest element in ArrayList

I have a sorted array. Given a key value (not necessarily in the table), I want to find the element in the table that is closes to the key value.

I have considered using a binary search, but I need to return the closest element if the key is not in the table (not -1). What should I try to do?

If there is no matches return -1. This is my current try with binary search:

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

Upvotes: 2

Views: 3764

Answers (5)

Konrad H&#246;ffner
Konrad H&#246;ffner

Reputation: 12207

Fortunately, the Java standard libraries include Arrays.binarySearch which gives you the "insertion point" of an element if it is not included in an array:

Returns: index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

With that we can implement your requirement very concisely:

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

Upvotes: 0

Sarath
Sarath

Reputation: 21

This will solve the question, to find the closest value, find the sum of the nearing index in the List, say for example {1,4,6,7,8,19} and key 3. the binary search will have the final subset with 1 and 4,

if (1+4 > 3+3) ? return 1 else return 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);
    }

Upvotes: 0

Puce
Puce

Reputation: 38132

Try something like (untested):

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

As said, this code is untested and you might have to check if it returns the correct value for all the corner cases.

Upvotes: 1

Colin D
Colin D

Reputation: 5661

Change:

if (first > last) return -1;

to 

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.

}

Upvotes: 1

Hipolith
Hipolith

Reputation: 461

When element at mid position isn't equal to key, You can calculate delta as abs(key-arr.get(mid)) and check whether it is lowest than actual delta (the lowest delta, the closest value You've got). In the end, if You don't find key in array, You return delta instead -1.

Notice, that You can NOT initialise delta with 0, because any later calculated delta will be greater than 0.

Upvotes: 0

Related Questions