相关疑难解决方法(0)

我们希望在复杂度不大于的循环排序数组中搜索给定元素O(log n).
示例:搜索13在{5,9,13,1,3}.

我的想法是将循环数组转换为常规排序数组,然后对结果数组进行二进制搜索,但我的问题是我提出的算法是愚蠢的,它O(n)在最坏的情况下采取:

for(i = 1; i < a.length; i++){
    if (a[i] < a[i-1]){
        minIndex = i; break;
    }
}

那么第i个元素的相应索引将由以下关系确定:

(i + minInex - 1) % a.length

很明显,我的转换(从循环到常规)算法可能需要O(n),所以我们需要一个更好的.

根据ire_and_curses的想法,这是Java中的解决方案:

public int circularArraySearch(int[] a, int low, int high, int x){
    //instead of using the division op. (which surprisingly fails on big numbers)
    //we will use the unsigned right shift to get the average
    int mid = (low + high) >>> 1; …

我有以下Java代码:

import java.util.Arrays;
import java.util.Collections;

public class Test {
    public static void main(String[] args) {
        int[] test = {1,2,3,4,5};
        Collections.rotate(Arrays.asList(test), -1);
        for(int i = 0; i < test.length; i++) { System.out.println(test[i]); }
    }

}

我想要旋转数组,但我得到的输出是

1
2
3
4
5

为什么是这样？

还有替代解决方案吗？

编辑:

这样可行:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        int[] test = {1,2,3,4,5};
        List<Integer> testList = new ArrayList<Integer>();
        for(int i = 0; i < test.length; i++) { testList.add(test[i]); } …

我正在寻找一个在Java中工作的高效公式,它计算以下表达式:

(low + high) / 2

用于二进制搜索.到目前为止,我一直在使用"低+(高 - 低)/ 2"和"高 - (高 - 低)/ 2"来避免某些情况下的溢出和下溢,但不是两者都有.现在我正在寻找一种有效的方法,可以用于任何整数(假设整数范围从-MAX_INT - 1到MAX_INT).

更新:结合Jander和Peter G.的答案并进行实验一段时间我得到了中值元素及其近邻的以下公式:

最低中点(等于floor((low + high)/2),例如[2 3] - > 2,[2 4] - > 3,[-3 -2] - > -3)

mid = (low & high) + ((low ^ high) >> 1);

最高中点(等于ceil((low + high)/2),例如[2 3] - > 3,[2 4] - > 3,[-3 -2] - > -2)

low++;
mid = (low & high) + ((low ^ high) >> 1);

中 - 前点(等于 …