在排序数组中找到第一个小于目标的元素

Question

在排序数组中，您可以使用二进制搜索来执行许多不同类型的操作：

找到第一个小于目标的元素
找到第一个比目标大的元素或者，
找到小于或等于目标的第一个元素
找到大于或等于目标的第一个元素甚至具体
找到最接近目标的元素。

你可以在stack overflow中找到#2和#5的答案，它们的答案是使用二分查找的变异，但是没有固定的算法来回答这些问题，特别是在调整索引方面。

例如第3题，找到排序数组中第一个小于或等于target的元素：给定 int[] stocks = new int[]{1, 4, 3, 1, 4, 6};，我想找到第一个小于 5 的元素。排序后应该是 return 4，我的代码如下：

private static int findMin(int[] arr, int target) {
    Arrays.sort(arr);
    int lo = 0;
    int hi = arr.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] > target) {
            hi = mid - 1;
        } else {
            lo = mid;
        }
    }
    return lo;
}

这里的逻辑是：

如果你发现 mid 元素等于目标，你只是 return mid
如果你发现 mid 元素比目标大，你就丢弃 mid 和所有比它大的东西
如果你发现中间元素小于目标，中间元素可能是一个答案，你想保留它，但丢弃任何小于它的东西。

如果你运行它，它实际上会进入一个无限循环，但只需将hi = arr.length - 1的起始索引调整为hi = arr.length;，它实际上工作得很好。我不知道如何真正设置所有条件：如何编写条件，如何设置 hi 和 lo 的起始索引以及使用 lo<=hi 或 lo < hi.

有什么帮助吗？

Answer 1

基本上在上面提到的情况下，你需要小于给定值的最大元素，即你需要找到给定元素的下限。这可以在 O(logn) 中使用二进制搜索轻松完成，时间：

您需要考虑的情况如下：

如果最后一个元素小于 x，则比 return 最后一个元素小。
如果中间点是floor，比returnmid.
如果在上述两种情况下都没有找到元素，则检查元素是否位于mid 和mid -1 之间。如果是 return mid-1.
否则继续在左半边或右半边迭代，直到找到满足条件的元素。 Select 右半边或左半边基于检查给定值大于 mid 还是小于 mid。

尝试以下操作：

static int floorInArray(int arr[], int low, int high, int x)
{
    if (low > high)
        return -1;

    // If last element is smaller than x
    if (x >= arr[high])
        return high;

    // Find the middle point
    int mid = (low+high)/2;

    // If middle point is floor.
    if (arr[mid] == x)
        return mid;

    // If x lies between mid-1 and mid
    if (mid > 0 && arr[mid-1] <= x && x < arr[mid])
        return mid-1;

    // If x is smaller than mid, floor
    // must be in left half.
    if (x < arr[mid])
        return floorInArray(arr, low, mid - 1, x);

    // If mid-1 is not floor and x is
    // greater than arr[mid],
    return floorInArray(arr, mid + 1, high,x);
}

Answer 2

在您的 while 循环中，您没有为 when hi == lo

设置大小写

这种情况适用于迭代最后一个元素或数组只有 1 个元素的情况。

设置while循环为while(lo <= hi)，搜索完所有元素后结束

或者在 hi 等于 lo.

时设置一个 if case 内部循环

if(hi == lo)

Answer 3

您可以只使用 Arrays.binarySearch(int[] a, int key)，然后相应地调整 returned 值，而不是实现您自己的二分查找。

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.

当有多个有效选择时（#3 或#4 具有多个相等值，或#5 具有等距值），您的规则没有指定 return 的索引，因此下面的代码有代码做出明确的选择。如果您不关心歧义，您可以删除多余的代码，或者如果您不同意我解决它的决定，则可以更改逻辑。

注意当return的值<0时，returnValue = -insertionPoint - 1表示insertionPoint = -returnValue - 1，在下面的代码中表示-idx - 1。因此，插入点之前的索引 是 -idx - 2.

这些方法当然可能 return 超出范围的索引值（-1 或 arr.length），因此调用者始终需要检查这一点。对于 closest() 方法，只有当数组为空时才会发生这种情况，在这种情况下它 returns -1.

public static int smaller(int[] arr, int target) { int idx = Arrays.binarySearch(arr, target); if (idx < 0) { // target not found, so return index prior to insertion point return -idx - 2; } // target found, so skip to before target value(s) do { idx--; } while (idx >= 0 && arr[idx] == target); return idx; } public static int smallerOrEqual(int[] arr, int target) { int idx = Arrays.binarySearch(arr, target); if (idx < 0) { // target not found, so return index prior to insertion point return -idx - 2; } // target found, so skip to last of target value(s) while (idx < arr.length - 1 && arr[idx + 1] == target) { idx++; } return idx; } public static int biggerOrEqual(int[] arr, int target) { int idx = Arrays.binarySearch(arr, target); if (idx < 0) { // target not found, so return index of insertion point return -idx - 1; } // target found, so skip to first of target value(s) while (idx > 0 && arr[idx - 1] == target) { idx--; } return idx; } public static int bigger(int[] arr, int target) { int idx = Arrays.binarySearch(arr, target); if (idx < 0) { // target not found, so return index of insertion point return -idx - 1; } // target found, so skip to after target value(s) do { idx++; } while (idx < arr.length && arr[idx] == target); return idx; } public static int closest(int[] arr, int target) { int idx = Arrays.binarySearch(arr, target); if (idx >= 0) { // target found, so skip to first of target value(s) while (idx > 0 && arr[idx - 1] == target) { idx--; } return idx; } // target not found, so compare adjacent values idx = -idx - 1; // insertion point if (idx == arr.length) // insert after last value return arr.length - 1; // last value is closest if (idx == 0) // insert before first value return 0; // first value is closest if (target - arr[idx - 1] > arr[idx] - target) return idx; // higher value is closer return idx - 1; // lower value is closer, or equal distance }

测试

public static void main(String... args) { int[] arr = {1, 4, 3, 1, 4, 6}; Arrays.sort(arr); System.out.println(Arrays.toString(arr)); System.out.println(" | Index | Value |"); System.out.println(" | < <= ~ >= > | < <= ~ >= > |"); System.out.println("--+----------------------+---------------------+"); for (int i = 0; i <= 7; i++) test(arr, i); } public static void test(int[] arr, int target) { int smaller = smaller (arr, target); int smallerOrEqual = smallerOrEqual(arr, target); int closest = closest (arr, target); int biggerOrEqual = biggerOrEqual (arr, target); int bigger = bigger (arr, target); System.out.printf("%d | %3d %3d %3d %3d %3d |%3s %3s %3s %3s %3s | %d%n", target, smaller, smallerOrEqual, closest, biggerOrEqual, bigger, (smaller < 0 ? "" : String.valueOf(arr[smaller])), (smallerOrEqual < 0 ? "" : String.valueOf(arr[smallerOrEqual])), (closest < 0 ? "" : String.valueOf(arr[closest])), (biggerOrEqual == arr.length ? "" : String.valueOf(arr[biggerOrEqual])), (bigger == arr.length ? "" : String.valueOf(arr[bigger])), target); }

输出

[1, 1, 3, 4, 4, 6] | Index | Value | | < <= ~ >= > | < <= ~ >= > | --+----------------------+---------------------+ 0 | -1 -1 0 0 0 | 1 1 1 | 0 1 | -1 1 0 0 2 | 1 1 1 3 | 1 2 | 1 1 1 2 2 | 1 1 1 3 3 | 2 3 | 1 2 2 2 3 | 1 3 3 3 4 | 3 4 | 2 4 3 3 5 | 3 4 4 4 6 | 4 5 | 4 4 4 5 5 | 4 4 4 6 6 | 5 6 | 4 5 5 5 6 | 4 6 6 6 | 6 7 | 5 5 5 6 6 | 6 6 6 | 7

Answer 4

试试树集。如果您的输入是数组，请按照以下步骤操作：

将数组转换为哈希集。来源：https://www.geeksforgeeks.org/program-to-convert-array-to-set-in-java/ 2.convert 哈希集为树集。树集将按无重复的排序顺序存储值。
现在，根据您的要求调用 Tree set 方法，例如 higher()、ceiling()、floor()、lower() 方法。

在排序数组中找到第一个小于目标的元素

Find the first element in a sorted array that is smaller than the target

java

arrays

binary-search