按值和索引搜索数组

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) {

    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);

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);

二分查找是查找数字的出现，如果没有找到则返回数字的索引，如果数字将被添加到排序列表中。