按值和索引搜索数组

我有一个排序的整数数组,我想对其执行搜索。这个数组可以有重复的值。如果我搜索一个重复的元素,那么它应该返回元素的第一个实例的索引。


如果我使用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

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


翻翻过去那场雪
浏览 243回答 3
3回答

撒科打诨

为什么不充分利用二分搜索和线性搜索呢?使用二进制搜索,获得的指数的你的电话号码的发生,然后线性搜索从那里后发现先发生: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);

小唯快跑啊

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);二分查找是查找数字的出现,如果没有找到则返回数字的索引,如果数字将被添加到排序列表中。
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

Java