给定一个已排序的数组(按绝对值排序)和一个数字，找到该数字的位置

Question

假设我们有一个数组

a[] ={1,2,-3,3,-3,-3,4,-4,5}

并找到3的位置(应该是3)

答案没有多个索引。

它必须是有效的，并且不是线性的。

我在考虑对数组进行二进制搜索，但不是比较原始值，而是比较绝对值；abs(ai)和abs(n) n是输入数字。然后，如果值相等，我再做一次比较，现在是原始值ai和n。

但我遇到了一个问题，如果我在上面的情况下使用相同的数组{1,2，- 3，3，-3，-3,4，5}，并且正在寻找3，那么就会有多个-3挡路(因此，我必须检查原始值ai和n是否不起作用，我必须检查ai+1和ai-1)。

好的，我现在只是漫无边际。我是不是想得太多了？

帮帮我谢谢！:D

Answer 1

这是一个改进的二进制搜索问题。这与常规的二进制搜索的不同之处在于，您需要查找并测试根据排序标准比较相等的所有元素。

我会：

• 使用调整过的二进制搜索算法来查找最左侧元素的索引，该算法会遍历索引，直到找到要查找的元素为止，或者查找绝对值不再匹配的元素。

对于第一步，这应该是O(logN)。如果假设元素值是均匀分布的，则第二步平均为O(1)。(第二步的最坏情况是O(N)；例如，当所有元素都有相同的绝对值，而您想要的元素是数组中的最后一个。)

Answer 2

以下是解决问题的方法：

/**
 * @param a array sorted by absolute value
 * @param key value to find (must be positive)
 * @return position of the first occurence of the key or -1 if key not found
 */
public static int binarySearch(int[] a, int key) {
    int low = 0;
    int high = a.length-1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = Math.abs(a[mid]);

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key || (midVal == key && mid > 0 && Math.abs(a[mid-1]) == key))
            high = mid - 1;
        else
            return mid; // key found
    }
    return -1; // key not found.
}

它是对JDK中的Arrays.binarySearch的修改。有几个变化。首先，我们比较绝对值。其次，由于您不需要任何键位置，而是第一个键位置，所以我修改了一个条件:如果我们找到一个键，则检查前一个数组项是否具有相同的值。如果是，那么我们继续搜索。这种方式的算法仍然保持O(log N)，即使在特殊情况下，有太多的值等于键。