Поиск массива по значению и индексу

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)) (для списка Pair s) вернул бы 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 sто же самое, тогда порядок определяется с помощью index.

Мой вопрос: можно ли сделать это менее грязным способом?Все, что короче, будет с благодарностью!

Answer 1

Посмотрите на фрагмент кода ниже.Внесены изменения в исходный двоичный код поиска: 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 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

Почему бы не использовать все возможности двоичного поиска и линейного поиска?Используйте бинарный поиск, чтобы получить индекс и вхождения вашего номера, а затем выполнить линейный поиск оттуда, чтобы найти 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 4

Просто хакерское решение.

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

Если ваш вопрос касается только массива 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).