查找排序的一维数组中元素的最近/最接近的下限值

Question

我想知道是否有可能在非空排序数组中找到可能存在或不存在的元素的最接近的下层元素。元素也可以重复任意次数。数组的所有元素 +ve。

例如，如果我们有值 [2,5,6,7,7,8,9]，并且我们正在寻找最接近 6 的元素，它应该返回 5，因为 5 是数组中最大的数字，小于 6。 同样，如果我们正在寻找最接近 9 的元素，它应该返回 8，因为 8 是数组中最大的数字，小于 9。 如果没有找到最接近的下元素，则返回 -1，就像我们正在寻找最接近 1 的元素一样，它应该返回 -1，因为没有这样的元素可以小于 1。这里 -1 表示在最接近元素的数组中不存在这样的值

我已经尝试了下面的代码。没事吧？如果我错过了什么，请帮助我。Java代码会更有帮助。

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

Answer 1

存在一个标准的二进制搜索函数。

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

如果未找到，则删除插入位置的 1 补码，如上所示。这意味着当结果为负数时，找不到该项目。

它或多或少地做了你所做的，但在没有找到时，它巧妙地返回一个负数：~ 插入位置(或 -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];
}

或者，由于int是离散的：

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

Answer 2

使用流：

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