按值和索引搜索数组

Question

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

如果我使用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。我之前通过 class 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 的列表）将 return 一个 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

您可以尝试创建自己的二进制搜索功能，除非我们正在搜索的数字第一次出现（之前的数字不同），否则不会停止搜索

试试这个二进制搜索功能：

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

二进制搜索正在寻找数字的出现，如果没有找到returns数字的索引，如果数字将被添加到排序列表中。

Answer 4

为什么不充分利用二进制搜索和线性搜索？使用二进制搜索获取您的号码 an 出现的索引，然后从那里线性搜索以找到 first 出现：

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 5

只需找到索引并向后搜索以找到第一个（如果存在）。这将是 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 6

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

按值和索引搜索数组

Searching an array by value and index

java

arrays

search

binary-search