当数组的一部分被反转时的二进制搜索-Java 学习之路

给定一个数组（大小为N）（已排序但其中某些部分被反转），以及一系列元素（Q），我们必须根据元素是否存在于数组中来输出是/否 .

我提出的解决方案如下：

执行线性遍历并找出数组被反转的索引 .
对于每个元素查询，在3个子数组（第一个子数组，反向子数组和剩余子数组）上调用二进制搜索

时间复杂度是 O(N + Q* log N). 我想知道我们是否可以在 O(Q * Log N) 中避免第一步？

3 回答

0

你知道这个数组包括三个部分，升序，降序，升序 . 所以你可以通过抽样找到两个关键点 . 这有点棘手，一旦你在反转部分找到一个点就足够了（只需要两次二进制搜索） . 找到反转部分更难 . 如果我们采样和数组[i 1] <array [i]，我们就找到了它 . 但如果我们错过它，我们不知道我们是太高还是太低，所以我们需要一个有间隔的队列来测试 . 我们从一个间隔开始，然后对中间进行采样 . 这给了我们两个区间，所以我们对它们的中间进行采样，给出了四个区间，依此类推，直到我们找到了反转区间的索引 .

回复于 2024-04-29T04:09:48+08:00

我想我找到了解决方案 . 首先我们需要的是找到一个突破点的某种方式，我的意思是：让我们说我们有一个数组{1,2,3,4,9,8,7,6}注意数字9在索引4处，它是一个突破点，因为排序方向已经改变，现在重要的部分是在log（n）中找到它 . 为此，我创建了以下类 . 为了使这个类工作，他需要得到一个数组以下类型{sorted，reverseSorted}

public class BreakPointSearcher {
private int array[];
private BiFunction<Integer, Integer, Boolean> compare;
private Map<Boolean, Direction> directions;

public BreakPointSearcher(int[] array, BiFunction<Integer, Integer, Boolean> compare) {
    this.array = array;
    this.compare = compare;
}

public int findTheBreackingPoint(int start, int end) {
    if (start >= end || end >= array.length)
        return -1;

    loadDirectionMap(start, end);
    int mid = (start + end) / 2;
    if (isBreackingPoint(mid))
        return mid;

    Direction direction = getDirection(mid);
    //Using recursive call by that making the algorithm run in O(log(n))
    if (GoRight == direction) {
        return findTheBreackingPoint(mid + 1, end);
    } else if (GoLeft == direction) {
        return findTheBreackingPoint(start, mid - 1);
    }

    return -1;
}

/**
 * I assume that two sides of the array have opposite sorting
 * that is if at the start we have ascending at the end we have descending
 */
private void loadDirectionMap(int start, int end) {
    directions = new HashMap<>();
    directions.put(compare.apply(array[start], array[start + 1]), GoRight);
    directions.put(compare.apply(array[end - 1], array[end]), GoLeft);
}

private Direction getDirection(int mid) {
    return directions.get(compare.apply(array[mid], array[mid + 1]));
}

private boolean isBreackingPoint(int mid) {
    boolean inBetween = compare.apply(array[mid - 1], array[mid]) && compare.apply(array[mid + 1], array[mid]); // a > b < c
    boolean inBetweenTypeTwo = compare.apply(array[mid], array[mid - 1]) && compare.apply(array[mid], array[mid + 1]); // a < b > c
    return inBetween || inBetweenTypeTwo;
}

enum Direction {
    GoLeft,
    GoRight
}

public static void main(String... args) {
    int[] arrayNums = {1, 2, 3, 4, 5, 6, 7, 20, 9, 8};
    BiFunction<Integer, Integer, Boolean> compareAsc = (a, b) -> a > b;
    BreakPointSearcher sbs = new BreakPointSearcher(arrayNums, compareAsc);
    System.out.println(sbs.findTheBreackingPoint(0, arrayNums.length - 1)); //output is 7

    arrayNums = new int[]{252, 48, 22, 10, 12, 13, 16};
    sbs = new BreakPointSearcher(arrayNums, compareAsc);
    System.out.println(sbs.findTheBreackingPoint(0, arrayNums.length - 1)); //output 3

    arrayNums = new int[]{22, 56, 13};
    sbs = new BreakPointSearcher(arrayNums, compareAsc);
    System.out.println(sbs.findTheBreackingPoint(0, arrayNums.length - 1)); //output 1

    arrayNums = new int[]{22, 56, 78, 33};
    sbs = new BreakPointSearcher(arrayNums, compareAsc);
    System.out.println(sbs.findTheBreackingPoint(0, arrayNums.length - 1)); //output 2

    arrayNums = new int[]{1, 2, 3, 4};
    sbs = new BreakPointSearcher(arrayNums, compareAsc);
    System.out.println(sbs.findTheBreackingPoint(0, arrayNums.length - 1)); //output -1

    arrayNums = new int[]{4, 3, 2, 1};
    sbs = new BreakPointSearcher(arrayNums, compareAsc);
    System.out.println(sbs.findTheBreackingPoint(0, arrayNums.length - 1)); //output -1

}

}

现在我们有了这样的类，我们可以开始二进制搜索，我要做的是搜索键，如果发现函数已经完成，如果在某些时候算法注意到排序被反转它将会向左移动在那一点的右侧，将搜索反转数组的边界，之后我们每个都有3个数组，我们执行二进制搜索（其中一个是反向的），就是它 . 它不是一个完美的解决方案，可能会在一些特殊情况下，但作为一般idia我认为这是正确的

public class SpecialBinarySearch {

private static BiFunction<Integer, Integer, Boolean> ascComp = (a, b) -> a > b;
private static BiFunction<Integer, Integer, Boolean> dscComp = (a, b) -> a < b;

public static int search(int[] array, int key, int start, int end, BiFunction<Integer, Integer, Boolean> compare) {
    int mid = (start + end) / 2;
    if (array[mid] == key)
        return mid;
    if (start == end)
        return -1;

    boolean opositeSorted = compare.apply(array[mid], array[mid + 1]);
    if (opositeSorted) {
        BreakPointSearcher breakPointSearcher = new BreakPointSearcher(array, compare);
        int leftBound = breakPointSearcher.findTheBreackingPoint(0, mid);
        int rightBound = breakPointSearcher.findTheBreackingPoint(mid, array.length - 1);

        leftBound = leftBound == -1 ? 0 : leftBound; //
        rightBound = rightBound == -1 ? array.length - 1 : rightBound;

        int opt1 = search(array, key, leftBound, rightBound, getOpositeCompare(compare));
        int opt2 = search(array, key, start, leftBound, compare);
        int opt3 = search(array, key, rightBound, end, compare);

        return Math.max(Math.max(opt1, opt2), opt3);
    }

    if (compare.apply(key, array[mid])) {
        return search(array, key, mid + 1, end, compare);
    } else {
        return search(array, key, start, mid - 1, compare);
    }
}

private static BiFunction<Integer, Integer, Boolean> getOpositeCompare(BiFunction<Integer, Integer, Boolean> compare) {
    return compare == ascComp ? dscComp : ascComp;
}

public static void main(String... args) {
    int[] array = {1, 2, 3, 20, 25};
    System.out.println(search(array, 20, 0, array.length - 1, ascComp)); //output 3

    array = new int[]{10, 9, 8, 7, 6, 3};
    System.out.println(search(array, 6, 0, array.length - 1, dscComp));//output 4

    array = new int[]{1, 2, 3, 4, 5, 20, 19, 18, 17, 16};
    System.out.println(search(array, 18, 0, array.length - 1, ascComp));//output 7

    array = new int[]{1, 2, 3, 4, 5, 20, 19, 18, 22, 25};
    System.out.println(search(array, 22, 0, array.length - 1, ascComp));//output 8

    array = new int[]{1, 2, 3, 4, 5, 20, 19, 18, 17, 16};
    System.out.println(search(array, 16, 0, array.length - 1, ascComp));//output 9

    array = new int[]{1, 2, 3, 4, 5, 20, 19, 18, 17, 16};
    System.out.println(search(array, 2, 0, array.length - 1, ascComp));//output 1

}

}

回复于 2024-04-29T04:09:48+08:00

0
它可以在 log(n) 中完成：

可能主要有3种情况：反向子阵列共享两半（1 5 4 3 2 6 7）或完全位于上半部分（1 3 2 4 5 6 7）或下半部分（1 2 3 4 6 5 7） .

1）最初，只需经过正常的二分查找并继续搜索，直到

（i）你找到了所需的元素或
（ii）您遇到反转的子数组（即当索引（l h）/ 2处的元素小于prev_element且大于next_element时） .
如果遇到反向子数组，则继续 2).

2）当反向子阵列共享两半时，即通过中间索引切换，则这是 pivoted array approach 的情况 . 对于 both 数组的第一个和第二个半部分应用下面提到的旋转数组方法，并查看是否找到了元素 .
2 * log（n）~log（n） .
确保也处理角落情况 .

Overall time complexity: log(n)

Pivoted array approach:

请记住，仍然会对数组的一半进行排序 . 因此，您仍然可以通过稍微修改二进制搜索在 log(n) 中找到该元素 .
```
Input arr[] = {3, 4, 5, 1, 2}
Element to Search = 1
 1) Find middle point mid = (l + h)/2
 2) If key is present at middle point, return mid.
 3) Else If arr[l..mid] is sorted
    a) If key to be searched lies in range from arr[l]
       to arr[mid], recur for arr[l..mid].
    b) Else recur for arr[mid+1..r]
 4) Else (arr[mid+1..r] must be sorted)
    a) If key to be searched lies in range from arr[mid+1]
       to arr[r], recur for arr[mid+1..r].
    b) Else recur for arr[l..mid]
```
关于www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/非常好的文章
回复于 2024-04-29T04:09:48+08:00

当数组的一部分被反转时的二进制搜索

3 回答

相关问题