Бинарный поиск, если массив содержит дубликаты

Question

Привет,

каков индекс ключа поиска, если мы ищем 24 в следующем массиве с использованием бинарного поиска.

array = [10,20,21,24,24,24,24,24,30,40,45]

У меня есть сомнения относительно бинарного поиска, что как он работает, если массив имеет повторяющиеся значения. Может кто-нибудь уточнить ...

Answer 1

Массив, который вы предложили, имеет среднее значение в среднем индексе, и в наиболее эффективных реализациях вернет это значение до первого уровня рекурсии.Эта реализация вернет '5' (средний индекс).

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

public class BinarySearch {
    public static int binarySearch(int[] array, int value, int left, int right) {
          if (left > right)
                return -1;
          int middle = left + (right-left) / 2;
          if (array[middle] == value)
                return middle;
          else if (array[middle] > value)
                return binarySearch(array, value, left, middle - 1);
          else
                return binarySearch(array, value, middle + 1, right);           
    }

    public static void main(String[] args) {
        int[] data = new int[] {10,20,21,24,24,24,24,24,30,40,45};

        System.out.println(binarySearch(data, 24, 0, data.length - 1));
    }
}

Answer 2

Как указывает @Pleepleus, он вернет индекс 5 с первого уровня самой рекурсии.Однако я хотел бы отметить несколько вещей о бинарном поиске:

1. Вместо использования mid = (left + right)/2, используйте mid = left + (right-left)/2

2. Если вы хотите найти lower_bound или upper_bound элемента используют следующие алгоритмы:

   binLowerBound(a, lo, hi, x)
     if (lo > hi)
       return lo;
   
     mid = lo +  (hi - lo) / 2;
     if (a[mid] == x)
       return binLowerBound(a, lo, mid-1, x);
     else if (a[mid] > x)
       return binLowerBound(a, lo, mid-1, x);
     else
       return binLowerBound(a, mid+1, hi, x);
   
   binHigherBound(a, lo, hi, x)
     if (lo > hi)
       return lo;
     mid = lo + (hi - lo) / 2;
     if (a[mid] == x)
       return binHigherBound(a, mid+1, hi, x);
     else if (a[mid] > x)
       return binHigherBound(a, lo, mid-1, x);
     else
       return binHigherBound(a, mid+1, hi, x);
   

Answer 3

public class a{
    public static int binarySearch(int[] array, int value, int left, int right) {
          if (left > right)
                return -1;
          int middle = (left + right) / 2;
          if (array[middle] == value)
        {
            if(array[middle-1]<array[middle])
                return middle;
                 //return binarySearch(array, value, left, middle - 1);
                 else
                return binarySearch(array, value, left, middle - 1);
        }
          else if (array[middle] > value)
                return binarySearch(array, value, left, middle - 1);
          else
                return binarySearch(array, value, middle + 1, right);           
    }
public static int binarySearch1(int[] array, int value, int left, int right) {
          if (left > right)
                return -1;
          int middle = (left + right) / 2;
          if (array[middle] == value)
        {
            if(array[middle]<array[middle+1])
                return middle; 
                 else

                    return binarySearch1(array, value, middle + 1, right);           
        }
          else if (array[middle] > value)
                return binarySearch1(array, value, left, middle - 1);
          else
                return binarySearch1(array, value, middle + 1, right);           
    }

    public static void main(String[] args) {
        int[] data = new int[] {10,20,21,24,24,24,24,24,30,40,45};


        System.out.println(binarySearch(data, 24, 0, data.length - 1));     //First Index
        System.out.println(binarySearch1(data, 24, 0, data.length - 1));    //Last Index
    }
}