按值和索引搜索数组

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))（用于Pairs的列表）搜索时，将返回一个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工作原理是这样的：它有两个变量valueand index，它们是排序数组元素的值，以及数组中元素的索引。该compareTo方法被覆盖以允许Collections.binarySearch()执行比较。比较可以这样定义：

• 如果电流value更大或更小，则顺序由 决定value。

• 如果values 相同，则使用 决定顺序index。

我的问题是，这可以以一种不那么凌乱的方式完成吗？任何更短的，将不胜感激！

Answer 1

为什么不充分利用二分搜索和线性搜索呢？使用二进制搜索，获得的指数的你的电话号码的发生，然后线性搜索从那里后发现先发生：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) {&nbsp; &nbsp; if (A[idx - 1] != key)&nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; --idx;}if (idx < 0)&nbsp; &nbsp; System.out.println("Key " + key + " not found");else&nbsp; &nbsp; System.out.println("First index of key " + key + " is " + idx);

Answer 2

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);二分查找是查找数字的出现，如果没有找到则返回数字的索引，如果数字将被添加到排序列表中。