Использование двоичного поиска с отсортированным массивом с дубликатами

Ответ 1

Хорошо, если у вас действительно есть отсортированный массив, вы можете выполнить двоичный поиск, пока не найдете один из индексов, который вы ищете, и оттуда остальное должно быть легко найти, так как все они следуют для каждого другого.

После того, как вы нашли свой первый, вы найдете все экземпляры перед ним, а затем все экземпляры после него.

Используя этот метод, вы должны получить примерно O (lg (n) + k), где k - количество вхождений значения, которое вы ищете.

EDIT:

И, нет, вы никогда не сможете получить доступ ко всем значениям k во всем, чем O (k).

Второе редактирование:, чтобы я мог чувствовать, как будто я нахожу что-то полезное:

Вместо того, чтобы просто искать первое и последнее вхождения X, вы можете выполнить двоичный поиск первого появления и двоичный поиск последнего вхождения. что приведет к O (lg (n)). как только вы это сделаете, вы поймете, что все индексы также содержат X (при условии, что он отсортирован)

Вы можете сделать это, выполнив поиск, если значение равно x, И, если значение слева (или справа в зависимости от того, смотрите ли вы для первого вхождения или последнего вхождения) равно x.

Ответ 2

Вы получите результат в O (lg n)

public static void PrintIndicesForValue(int[] numbers, int target) {
    if (numbers == null)
        return;

    int low = 0, high = numbers.length - 1;
    // get the start index of target number
    int startIndex = -1;
    while (low <= high) {
        int mid = (high - low) / 2 + low;
        if (numbers[mid] > target) {
            high = mid - 1;
        } else if (numbers[mid] == target) {
            startIndex = mid;
            high = mid - 1;
        } else
            low = mid + 1;
    }

    // get the end index of target number
    int endIndex = -1;
    low = 0;
    high = numbers.length - 1;
    while (low <= high) {
        int mid = (high - low) / 2 + low;
        if (numbers[mid] > target) {
            high = mid - 1;
        } else if (numbers[mid] == target) {
            endIndex = mid;
            low = mid + 1;
        } else
            low = mid + 1;
    }

    if (startIndex != -1 && endIndex != -1){
        for(int i=0; i+startIndex<=endIndex;i++){
            if(i>0)
                System.out.print(',');
            System.out.print(i+startIndex);
        }
    }
}

Ответ 3

public void PrintIndicesForValue42(int[] sortedArrayOfInts) {
    int index_occurrence_of_42 = left = right = binarySearch(sortedArrayOfInts, 42);
    while (left - 1 >= 0) {
        if (sortedArrayOfInts[left-1] == 42)
            left--;
    }
    while (right + 1 < sortedArrayOfInts.length) {
        if (sortedArrayOfInts[right+1] == 42)
            right++;
    }
    System.out.println("Indices are from: " + left + " to " + right);
}

Это будет работать в O (log (n) + #occurrences) Читайте и понимайте код. Это достаточно просто.

Ответ 4

Hashmap может работать, если вам не требуется использовать двоичный поиск.

Создайте HashMap, где Key - это само значение, а затем значение представляет собой массив индексов, в котором это значение находится в массиве. Прокрутите массив, обновив каждый массив в HashMap для каждого значения.

Время поиска для индексов для каждого значения будет ~ O (1), а создание самой карты будет ~ O (n).

Ответ 5

Find_Key(int arr[], int size, int key){
int begin = 0;
int end = size - 1;
int mid = end / 2;
int res = INT_MIN;

while (begin != mid)
{
    if (arr[mid] < key)
        begin = mid;
    else
    {
        end = mid;
        if(arr[mid] == key)
            res = mid;
    }
    mid = (end + begin )/2;
}
return res;
}

Предполагая, что массив ints находится в порядке возрастания сортировки; Возвращает индекс первого индекса вхождения ключа или INT_MIN. Выполняется в O (lg n).

Ответ 6

Ниже приведен код Java, который возвращает диапазон, для которого ключ поиска распространяется в заданном отсортированном массиве:

public static int doBinarySearchRec(int[] array, int start, int end, int n) {
    if (start > end) {
        return -1;
    }
    int mid = start + (end - start) / 2;

    if (n == array[mid]) {
        return mid;
    } else if (n < array[mid]) {
        return doBinarySearchRec(array, start, mid - 1, n);
    } else {
        return doBinarySearchRec(array, mid + 1, end, n);
    }
}

/**
 * Given a sorted array with duplicates and a number, find the range in the
 * form of (startIndex, endIndex) of that number. For example,
 * 
 * find_range({0 2 3 3 3 10 10}, 3) should return (2,4). find_range({0 2 3 3
 * 3 10 10}, 6) should return (-1,-1). The array and the number of
 * duplicates can be large.
 * 
 */
public static int[] binarySearchArrayWithDup(int[] array, int n) {

    if (null == array) {
        return null;
    }
    int firstMatch = doBinarySearchRec(array, 0, array.length - 1, n);
    int[] resultArray = { -1, -1 };
    if (firstMatch == -1) {
        return resultArray;
    }
    int leftMost = firstMatch;
    int rightMost = firstMatch;

    for (int result = doBinarySearchRec(array, 0, leftMost - 1, n); result != -1;) {
        leftMost = result;
        result = doBinarySearchRec(array, 0, leftMost - 1, n);
    }

    for (int result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n); result != -1;) {
        rightMost = result;
        result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n);
    }

    resultArray[0] = leftMost;
    resultArray[1] = rightMost;

    return resultArray;
}

Ответ 7

Используется модифицированный двоичный поиск. Это будет O (LogN). Сложностью пространства будет O (1). Мы дважды вызываем BinarySearchModified. Один для поиска начального индекса элемента и другого для нахождения концевого индекса элемента.

private static int BinarySearchModified(int[] input, double toSearch)
    {
        int start = 0;
        int end = input.Length - 1;

        while (start <= end)
        {
            int mid = start + (end - start)/2;
            if (toSearch < input[mid]) end = mid - 1;
            else start = mid + 1;
        }

        return start;
    }


    public static Result GetRange(int[] input, int toSearch)
    {
        if (input == null) return new Result(-1, -1);

        int low = BinarySearchModified(input, toSearch - 0.5);

        if ((low >= input.Length) || (input[low] != toSearch)) return new Result(-1, -1);

        int high = BinarySearchModified(input, toSearch + 0.5);

        return new Result(low, high - 1);
    } 

 public struct Result
    {
        public int LowIndex;
        public int HighIndex;

        public Result(int low, int high)
        {
            LowIndex = low;
            HighIndex = high;
        }
    }

Ответ 8

Я придумал решение, используя двоичный поиск, только нужно делать бинарный поиск на обеих сторонах, если совпадение найдено.

public static void main(String[] args) {
    int a[] ={1,2,2,5,5,6,8,9,10};
    System.out.println(2+" IS AVAILABLE  AT = "+findDuplicateOfN(a, 0, a.length-1, 2));
    System.out.println(5+" IS AVAILABLE  AT = "+findDuplicateOfN(a, 0, a.length-1, 5));
    int a1[] ={2,2,2,2,2,2,2,2,2};
    System.out.println(2+" IS AVAILABLE  AT = "+findDuplicateOfN(a1, 0, a1.length-1, 2));

    int a2[] ={1,2,3,4,5,6,7,8,9};
    System.out.println(10+" IS AVAILABLE  AT = "+findDuplicateOfN(a2, 0, a2.length-1, 10));
}

public static String findDuplicateOfN(int[] a, int l, int h, int x){
    if(l>h){
        return "";
    }
    int m = (h-l)/2+l;
    if(a[m] == x){
        String matchedIndexs = ""+m;
        matchedIndexs = matchedIndexs+findDuplicateOfN(a, l, m-1, x);
        matchedIndexs = matchedIndexs+findDuplicateOfN(a, m+1, h, x);
        return matchedIndexs;
    }else if(a[m]>x){
        return findDuplicateOfN(a, l, m-1, x);
    }else{
        return findDuplicateOfN(a, m+1, h, x);
    }
}


2 IS AVAILABLE  AT = 12 
5 IS AVAILABLE  AT = 43 
2 IS AVAILABLE  AT = 410236578 
10 IS AVAILABLE  AT =

Я думаю, что это все еще дает результаты в сложности O (logn).

Ответ 9

public void printCopies(int[] array)
{
    HashMap<Integer, Integer> memberMap = new HashMap<Integer, Integer>();
    for(int i = 0; i < array.size; i++)
       if(!memberMap.contains(array[i]))
           memberMap.put(array[i], 1);
       else
       {
           int temp = memberMap.get(array[i]); //get the number of occurances
           memberMap.put(array[i], ++temp); //increment his occurance
       }

    //check keys which occured more than once
    //dump them in a ArrayList
    //return this ArrayList
 }

Альтернативно, вместо подсчета количества событий, вы можете поместить свои индексы в arraylist и поместить их на карту вместо count.

   HashMap<Integer, ArrayList<Integer>> 
   //the integer is the value, the arraylist a list of their indices

public void printCopies(int[] array)
{
    HashMap<Integer, ArrayList<Integer>> memberMap = new HashMap<Integer, ArrayList<Integer>>();
    for(int i = 0; i < array.size; i++)
       if(!memberMap.contains(array[i]))
       {
           ArrayList temp = new ArrayList();
           temp.add(i);
           memberMap.put(array[i], temp);
       }
       else
       {
           ArrayList temp = memberMap.get(array[i]); //get the lsit of indices
           temp.add(i);
           memberMap.put(array[i], temp); //update the index list
       }

    //check keys which return lists with length > 1
    //handle the result any way you want
 }

heh, я думаю, это должно быть опубликовано.

 int predefinedDuplicate = //value here;
 int index = Arrays.binarySearch(array, predefinedDuplicate);
 int leftIndex, rightIndex;
 //search left
 for(leftIndex = index; array[leftIndex] == array[index]; leftIndex--); //let it run thru it
 //leftIndex is now the first different element to the left of this duplicate number string
 for(rightIndex = index; array[rightIndex] == array[index]; rightIndex++); //let it run thru it

 //right index contains the first different element to the right of the string
 //you can arraycopy this [leftIndex+1, rightIndex-1] string or just print it
 for(int i = leftIndex+1; i<rightIndex; i++)
 System.out.println(array[i] + "\t");

Ответ 10

Еще один результат для двоичного поиска log (n) для самой левой цели и самой правой цели. Это на С++, но я думаю, что это вполне читаемо.

Идея состоит в том, что мы всегда оказываемся в left = right + 1. Итак, чтобы найти самую левую цель, если мы сможем переместить right на самое правое число, которое меньше цели, слева будет у самой левой цели.

Для самой левой цели:

int binary_search(vector<int>& nums, int target){
    int n = nums.size();
    int left = 0, right = n - 1;

    // carry right to the greatest number which is less than target.
    while(left <= right){
        int mid = (left + right) / 2;
        if(nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    // when we are here, right is at the index of greatest number
    // which is less than target and since left is at the next, 
    // it is at the first target index
    return left;
}

Для самой правой цели идея очень похожа:

int binary_search(vector<int>& nums, int target){
    while(left <= right){
        int mid = (left + right) / 2;
        // carry left to the smallest number which is greater than target.
        if(nums[mid] <= target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    // when we are here, left is at the index of smallest number
    // which is greater than target and since right is at the next, 
    // it is at the first target index
    return right;
}