java通过值和索引搜索数组

Question

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

如果我使用Arrays.binarySearch()，那么它不一定给出所搜索元素的第一个实例的索引。例如here：

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，它们是排序数组中元素的值，以及数组中元素的索引。重写compareTo方法以允许Collections.binarySearch()执行比较。比较可以这样定义：

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

我的问题是，这能以一种不那么混乱的方式完成吗？任何较短的都将不胜感激

Answer 1

如果您的问题只是处理数组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)

Answer 2

只要找到索引并向后搜索，找到第一个，如果它存在的话。这将是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;
}

Answer 3

只是一个骇人的解决方案

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

二进制搜索是查找数字的出现，如果未找到，则返回数字的索引，如果该数字将被添加到排序列表中

Answer 4

看看下面的代码。对原始二进制搜索代码进行了更改：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);
    }
}

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

Answer 6

为什么不充分利用二进制搜索和线性搜索呢？使用二进制搜索来获取数字的一个出现点的索引，然后从那里线性搜索回来，找到第一个出现点：

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