Нахождение элемента в массиве так, чтобы индекс был равен его значению, используя бинарный поиск - PullRequest
Новая
       5

Нахождение элемента в массиве так, чтобы индекс был равен его значению, используя бинарный поиск

1 голос
/ 11 марта 2020

У меня есть массив в порядке возрастания, состоящий из натуральных чисел и с условными дубликатами, не допускается. В массиве я должен найти m такой, что array[m]=m используя двоичный поиск, я использовал следующий код: 

public class Main {

public static void main(String[] args) {
    Scanner a = new Scanner(System.in);
    int n = a.nextInt();
    int arr[] = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = a.nextInt();
    }
    int result = binarysearch(arr,n);
    if(result!=-1)
        System.out.println(result);
    else
        System.out.println("NOT_FOUND");
}

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

Обратите внимание, что массив 1-индексирован, а не 0-индексирован. Проблема, с которой я сталкиваюсь, заключается в следующем: array={1,2,3,4,5} ожидаемый output is 1, но из-за двоичного поиска метод returns 3 в качестве вывода , Есть ли обходной путь для обхода этого типа дел?

Ответы [ 2 ]

2 голосов
/ 11 марта 2020

Глядя на условия: «У меня есть массив в порядке возрастания, состоящий из положительных целых чисел и с дубликатами условий, не допускаются» *

  1. в порядке возрастания
  2. положительные целые числа
  3. без дубликатов

Эта проблема имеет тривиальное решение. 

public static int binarysearch(int[] array,int n){
    If(a[0] == 1) return 1;
    else return -1;
}

Поскольку, если первое число в массиве не равно 1, остальная часть массива не будет иметь любое значение, равное его индексу.

Объяснение:

Предположим, что массив имеет термины a1, a2, a3 ... an, где не слагаемые равны, а aj

Проблема, по сути, заключается в нахождении термина ai, где ai = i

Если a1 не равен 1, он должен быть больше 1 в соответствии с условием # 2.

По условиям 1 и 3, a2 должно быть больше 2. Затем, a3 должно быть больше 3, и так далее. Срок должен быть больше чем n. Не дает решения.

С другой стороны, если a1 равно 1, у вас есть термин, и вы можете его вернуть.

1 голос
/ 11 марта 2020

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

Я думаю, что настоящая проблема заключается в понимании того, как работает бинарный поиск. Двоичный поиск всегда начинается в середине массива. Таким образом, если вы введете ввод {1, 2, 3, 4, 5}, вы всегда получите 3, потому что алгоритм начинается с поиска в середине и замечает, что число 3 равно его индексу.

Если ваша цель - найти наименьшее целое число m такое, что [m] равно m, тогда Вы не должны использовать бинарный поиск. Вместо этого вы должны начать с начала массива (так как мы предполагаем, что он отсортирован в порядке возрастания) и использовать линейный поиск: 

for (int i = 0; i < n; ++i) {
  if (a[i] == i) {
    return i;
  }
}
return -1;

Что-то похожее на приведенное выше должно дать ожидаемый результат. (Обратите внимание, что приведенное выше использует индексную логику на основе 0 c, но вы должны иметь возможность настраивать ее по мере необходимости. Кроме того, массивы в Java всегда индексируются 0, так что вы можете перепроверить, что вы понимаете проблема правильно.)

...