CODEWITHSUNDEEP
javaarrays
Sushovan Karmakar
Sushovan Karmakar

Reputation: 1

Find the nearest/closest lower value of an element in a sorted 1D array

I was wondering if it is possible to find the closest lower element in a non-empty sorted array for an element that may be there or may not be there. Elements can be repeated also any number of times. All elements of the array +ve.

For example, if we had the values [2,5,6,7,7,8,9] and we are looking for the element closest lower to 6, it should return 5, because 5 is the biggest number in the array, that is smaller than 6. Similarly, if we're looking for the element closest lower to 9, it should return 8, because 8 is the biggest number in the array, that is smaller than 9. And if the closest lower element is not found, return -1 like if we're looking for the element closest lower to 1, it should return -1, because there is no such element which can be lower than 1. Here -1 represents that there's no such value is present in the array which is closest lower to the element

I have tried this below code. Is it all right? If I'm missing something, please help me. Java code will be more helpful.

static int find(int[] a, int target)
{
    int n = a.length;

    if(target <= a[0])
        return -1;

    if(target > a[n-1])
        return a[n-1];

    int i=0,j=n,mid=0;

    while(i<j)
    {
        mid = (i+j)/2;
        if(target <= a[mid])
        {
            if( mid >0 & target> a[mid-1] )
            {   
                 return a[mid-1]; 
            }

            j= mid;
        }
        else
        {
            if( mid<(n-1) & target > a[mid+1] )
            {   
                 return a[mid+1]; 
            }

            i= mid+1;
        }
    }
    return mid;
}

Upvotes: 0

Views: 1462

Answers (2)

Joop Eggen
Joop Eggen

Reputation: 109613

There exists a standard binarySearch function.

static int find(int[] a, int target) {
    int position = Arrays.binarySearch(a, target);
    if (position >= 0) {
        System.out.println("Found at index " + position);
    } else {
        int insertIndex = ~position;
        System.out.println("Insert position at index " + insertIndex);
        position = insertIndex;
    }
    return position;
}

When not found it delives the ones-complement of the insert position, as shown above. This means when the result is negative, the item is not found.

It does more or less what you did, but on not finding, it cleverly return a negative: ~ insert position (or -insert position - 1).

/**
 * Search the next smaller array element.
 * @param a the array sorted in ascending order.
 * @param target the value to keep below.
 * @return the greatest smaller element, or -1.
 */
static int findNextSmaller(int[] a, int target) {
    int i= Arrays.binarySearch(a, target);
    if (i >= 0) {
        --i;
        while (i>= 0 && a[i] == target) {
            --i;
        }
    } else {
        i = ~i;
        --i;
    }
    return i == -1 ? -1 : a[i];
}

Or, as int is discrete:

static int findNextSmaller(int[] a, int target) {
    int i= Arrays.binarySearch(a, target - 1);
    if (i >= 0) {
        return target - 1;
    }
    i = ~i;
    --i;
    return i == -1 ? -1 : a[i];
}

Upvotes: 2

Lothar
Lothar

Reputation: 5459

Using streams:

import java.util.stream.IntStream;

public class FindNearestLowestValue {

    public final static void main(String[] args) {
        int[] array = {2,5,6,7,7,8,9};
        int searchVal = 6;
        // reverse the order so the first element of the filtered stream is the result
        System.out.println(
            IntStream.range(0, array.length)
                .map(i -> array[array.length - 1 - i])
                .filter(n -> n < searchVal)
                .findFirst().orElse(-1)
        );
    }
}

Upvotes: 0

Related Questions