通过值和索引搜索数组

Question

我有一个整数排序数组，想要在其上执行搜索。该数组可能具有重复的值。如果我搜索一个重复的元素，则应返回该元素第一次出现的索引。

如果我使用Arrays.binarySearch()，则不一定会给出搜索元素第一次出现的索引。例如可以看到这里:

int[] A = {10,20,21,24,24,24,24,24,30,40,45} ;
int idx = Arrays.binarySearch(A,24) ;

这里，idx 的值是 5。我想让它成为 3。我之前通过创建一个名为 Pair 的类来解决这个问题，代码如下：

class Pair implements Comparable<Pair>
{
    int value, index ;
    Pair(int v,int i)
    {
        this.value = v ;
        this.index = i ;
    }
    @Override
    public int compareTo(Pair p)
    {
        if(p.value<this.value)
            return 1 ;
        else if(p.value>this.value)
            return -1 ;
        else 
        {
            if(p.index<this.index)
                return 1 ;
            else if(p.index>this.index)
                return -1 ;
            else return 0 ;
        }
    }
}

当使用Collections.binarySearch(new Pair(24,Integer.MIN_VALUE))（对于一组Pair）进行搜索时，将返回3。代码如下：

int[] A = {10,20,21,24,24,24,24,24,30,40,45} ;

        List<Pair> L = new ArrayList<Pair>() ;

        for(int i=0;i<A.length;i++)
        {
            L.add(new Pair(A[i],i)) ;
        }
        int idx = Collections.binarySearch(L,new Pair(24,Integer.MIN_VALUE)) ;
        if(idx<0) idx = -idx-1 ;
        System.out.println(idx) ;

Pair的工作方式如下： 它有两个变量value和index，分别代表排序数组元素的值和元素在数组中的索引。为了让Collections.binarySearch()能够进行比较，重写了compareTo方法。比较可以按照以下方式定义：

• 如果当前value大于或小于，则按value决定顺序。
• 如果value相同，则使用index来决定顺序。

我的问题是，这种方式是否可以更简洁？任何更短的方法都将不胜感激！

- Mooncrater

Answer 1

请看下面的代码片段。对原有的二分查找代码进行了修改：l和r分别代表左右范围。

public static int binarySearch(int[] arr, int num, int l,int r) {
    int mid = (l+r)/2;
    if(arr[mid] == num && (mid>0&& arr[mid-1]!=num) || mid==0) {            
        return mid;
    }       
    else if(arr[mid] > num || (mid > l && arr[mid] == num && arr[mid-1] == num)) {
        return binarySearch(arr, num, l, mid);
    }else {
        return binarySearch(arr, num, mid, r);
    }
}

- Yug Singh

Answer 2

如果你的问题只涉及数组A，你可以使用下面的代码找到第一个索引：

    int[] A = { 10, 20, 21, 24, 24, 24, 24, 24, 30, 40, 45 };
    // key is a[i], value is the index
    Map<Integer, Integer> hmap = new HashMap<Integer, Integer>();

    for (int i = 0; i < A.length; i++) {
        hmap.putIfAbsent(A[i], i);
    }

如果数字已经存在，我们不会增加i的值，因为我们需要重复数字的第一个索引。这样重复数字的第一个索引始终保持不变。

现在要获取索引，我们只需要使用hmap.get（24）。

- Nicholas K

---

@Eugene 那条评论是针对NicholasK之前的回答的。我现在正在删除那条评论。 - Mooncrater

@NicholasK 这不错，可以简化为 for (int i = 0; i < A.length; i++) { hmap.putIfAbsent(A[i], i); }。但是，你只是迭代数组中的所有元素将它们放入映射表中，然后进行查找。这将是 O(n) + O(1) = O(n)。如果你正在迭代，可以使用简单的 if 条件语句来查找；这样你就完全忽略了有序数组的特性。 - Eugene

@Eugene：是的，同意。但查找是O(1)，所以想分享一下。 - Nicholas K

Answer 3

只是一个hacky的解决方案。

double[] A = { 10, 20, 21, 24, 24, 24, 24, 24, 30, 40, 45 };
int key = 24;
int idx = -(Arrays.binarySearch(A, key - 0.5) + 1);
if (A[idx] != key)
    System.out.println("Key not exist!");
else
    System.out.println("First occurance of key is " + idx);

二分查找是用来查找数字的，如果没有找到，则返回数字应该插入的位置的索引，前提是这个数字将被添加到已排序的列表中。

- drowny

---

美丽而聪明！ - Mooncrater

但这需要创建一个新的float数组（+ O(n)空间）。这可能需要手动编写3行代码，至少如此。但仍然是一个很好的答案。 - Mooncrater

感谢 @KevinAnderson 的建议，我已经更新了帖子。 - drowny

很高兴我能为这种愚蠢做出贡献 (;->) - Kevin Anderson

现在我们都是黑客了 ;) - drowny

Answer 4

为什么不充分利用二分查找和线性查找？使用二分查找获取您的数字出现的索引，然后从那里开始线性搜索以找到第一个出现的位置。请注意保留HTML标记。

int[] A = { 10, 20, 21, 24, 24, 24, 24, 24, 30, 40, 45 };
int key = 24;
int idx = Arrays.binarySearch(A, key);
while (idx > 0) {
    if (A[idx - 1] != key)
        break;
    --idx;
}
if (idx < 0)
    System.out.println("Key " + key + " not found");
else
    System.out.println("First index of key " + key + " is " + idx);

- Kevin Anderson

Answer 5

你可以尝试创建自己的二分查找函数，除非我们要搜索的数字是第一次出现（前面的数字不同），否则它不会停止搜索。

尝试使用以下二分查找函数：

public static int binarySearch(int[] arr,int x)
{
    int maxi=arr.length-1;
    int mini=0;
    int mid;
    while(mini<=maxi)
    {
        mid=(maxi+mini)/2;
        if(arr[mid]==x&&(mid==0||arr[mid-1]!=x))
        {
            return mid;
        }
        else if(arr[mid]<x)
        {
            mini=mid+1;
        }
        else
        {
            maxi=mid-1;
        }
    }
    return -1;
}

- Uri

---

谢谢您的回答，@Uri！我可以这样做，但这违背了我的问题的目的。我想要一个简洁地完成这个任务的方法。loc仍然大致相同。 - Mooncrater

Answer 6

只需找到索引，然后向后搜索以找到第一个存在的元素。如果存在，则时间复杂度为 O(log(n) + m)；其中 m 是数组中该元素出现的次数（该元素在数组中的重复次数）。

 private static int findFirstIndex(List<Pair> pairs, Pair search) {
    int idx = Collections.binarySearch(pairs, search);
    if (idx < 0) {
        return idx = -idx - 1;
    }

    for (; idx > 1; --idx) {
        if (pairs.get(idx - 1).compareTo(pairs.get(idx)) != 0) {
            return idx;
        }
    }

    return idx;
}

- Eugene