使用 BinarySearch 的变体在双调数组中查找最大值

Question

这是我的代码，其中 a 是要查找最大值的数组（每个元素都是不同的）。在我看来，如果a[mid]小于a[mid-1]那么最大值的位置应该在[lo, mid-1]范围内。然而，当我实现我的想法时，程序是无穷无尽的。解决方案是使用[lo, mid]作为下一次迭代。

我的问题是：为什么我不应该在第 9 行中使用 mid-1 而不是 mid？

第一次编辑：有人问我为什么不直接排序并选择第一个元素？因为问题是在双调数组中找到一个键（元素升序先下降）。我的解决方案是找到数组的最大值，将其分成两部分，分别使用 BinarySearch 找到键。如果我对数组进行排序，我将破坏原始顺序。

第二次编辑：详细添加更多代码和预期输出。

public static int getMaxIndex(int[] a) {
    int hi = a.length - 1;
    int lo = 0;
    while (lo < hi && a[lo] <= a[lo+1]) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > a[mid-1]) {
            lo = mid;
        } else {
            hi = mid - 1;  // Should be mid, not mid-1, why?
        }
    }
    return lo;
}

public static void main(String[] args) {
    int[] a = {1, 2, 3, 5, 7, 9, 8, 6, 4};  // Bitonic array
    System.out.println(getMaxIndex(a));  // Should be 5 
}

Answer 1

双调数组

数字严格递增，索引后数字严格递减

例如：[15, 20, 26, 5, 1]

如果数组仅包含唯一元素，则可以使用以下条件找到最大值

迭代 left index < right index
计算middle index（向左，以防没有单个中间索引）
如果中间的值小于下一个元素，则向右移动
否则向左向左移动

arr[mid] < arr[mid + 1] 永远不会抛出越界异常，因为 left < right 不变量在循环中保持不变。因此 mid(index) 总是小于 right(index) 因此在 mid

之后至少有一个索引

int left = 0, right = arr.length - 1;
while (left < right) {
  int mid = left + (right - left) / 2;
  if (arr[mid] < arr[mid + 1]) {
    left = mid + 1;
  } else {
    right = mid;
  }
}
return arr[left]; // or arr[right]


              15        20        26         5         1
l=0, r=4      l                   m                    r
m=2

a[m] > a[m+1] l                   r                  
so, r=m

l=0, r=2      l         m         r
m=1

a[m] < a[r+1]                      l,r
m=l+1

Now exit while loop l == r and return value at l or r

OP代码分析

一个简单的可重现示例是 [1, 2] - 这将导致 lo 卡在同一索引上并导致无限循环。
任何减少到 lo + 1 == hi 和 arr[lo] < arr[hi] 的数据集都会将 mid 设置为 lo（lo + (hi - lo) / 2 将是 lo），因此赋值 lo = mid 导致无限循环

Answer 2

这里，单词bitonic的意思是，数组按升序排序，在某个点（可能）之后它开始减少。

同样，你必须找到数组开始减少的支点（如果存在的话），如果你能找到那个点，that's it，这个支点就是你的答案。

所以我附上一些 input/output 序列以使其更清楚：

{1, 2, 3, 5, 7, 9, 8, 6, 4}; --> should  return 5 (index at which element is maximum)
{15, 20, 26, 5, 1} --> should return 2 (index at which element is maximum)
{0, 1, 2, 3} --> should return 3 (index at which element is maximum)

现在您必须像下面这样修改您的代码：

public static int getMaxIndex(int[] arr) {
    int  left = 0, right = arr.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if(mid == 0 || mid == arr.length-1) {
            // if no such pivotal point exist in sequence/array
            return mid;
        }else if(arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]){               
            // it's the pivotal point, where element at left side smaller and element at right side too
            return mid;
        }
      if (arr[mid] < arr[mid + 1]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    return -1;
}

Answer 3

你遇到的问题是你并不总是在改变 mid。在您的示例中，有一点 lo 是 4 并指向数组中的 7，而 hi 是 5 并指向 9。在lo和hi只相差1的情况下，mid设置为lo。这里你比较的是a[mid] > a[mid-1]。问题 1，mid-1 超出范围，在极少数情况下会给出 ArrayIndexOutOfBoundsException。其次，如果条件是 true，则将 lo 设置为 mid，这是它已有的值。你一事无成。您处于无限循环中。

我用

试过你的方法

    System.out.println(getMaxIndex(new int[] { 3 , 8 })); // Expecting 1

我得到了java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 2

解决方案在马的回答中。

使用 BinarySearch 的变体在双调数组中查找最大值

Using a Variant of BinarySearch to Find the Maximum in a Bitonic Array

java

algorithm

binary-search

双调数组

OP代码分析