Помогите найти ошибку в методе

267
13 декабря 2018, 03:00

Есть массив заполненный числами от 1 до 100 с пропущенным числом 46, путем сложения первого и последнего элемента идет поиск пропущенного элемента, по неизвестной мне причине ничего не работает, переменная end не уменьшается.

public static void main(String ...args) {
    int[] sor={};
    sor=init(sor, 99, 46);
    System.out.println(searchBin(sor));
}
public static int[] init(int [] ar,int lenght,int val){
    ar= new int[lenght];
    for(int i1=0,i=1;i<=ar.length+1;i1++,i++){
        if(i==val) {
            i1--;
            val=0;
            continue;
        }
        ar[i1]=i;
    }
    return ar;
}
public static int searchBin(int[] ar){
    int start=ar[0];//1
    int end=ar[ar.length-1];//100
    int sum=start+end;//101
    int r=sum;//101
    while(r==sum){//true
        start++;//2
        end--;//99
        start= ar[start-1];//2
        end  = ar[end-1];//здесь значение возвращается на с 99 на 100
        r=start+end;//101
    }
    return start;
}
Answer 1

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

Подумайте на бумаге для маленького массива, как всё должно быть.
Пусть длина = 5 и исключается число val=3

i    0  1  2  3  4
ar   1  2  4  5  6

Т.е. достаточно для малых индексов записывать i+1, а для больших i+2, начиная с индекса i-1. Если в java есть тернарный оператор, цикл вообще будет в две строчки.

public static int[] init(int lenght,int val){
    int[] ar = new int[lenght];
    for(int i=0; i<ar.length;i++){
        if(i<val-1) 
            ar[i] = i + 1;
        else
            ar[i] = i + 2;
    }
    return ar;
}

А вот метод поиска в таком виде полноценно работать не будет. Если даже нашли пару, то нужно ещё проверять, какой элемент из пары нарушает порядок.

Название, вообще говоря, подразумевает бинарный поиск.
Если опираться на то, что входной массив сформирован корректно, то бинарный поиск, который будет искать самый левый элемент после разрыва, будет довольно прост:

public static int searchBin(int[] ar){
    int l = 0;
    int r = ar.length-1;
    int m;
    while( l < r) {
        m = (l + r) >>> 1;   //среднее значение
        if (ar[m] == m + 2)   //мы в правой части
             r = m;
        else
             l = m + 1;
    }
    return l + 1;
  }  

Рабочий код тут

Answer 2

У вас была ошибка в алгоритме. Вот рабочий код:

public static void main(String[] args) {
        int[] sor={};
    sor=init(sor, 99, 43);
    System.out.println(searchBin(sor));
}
public static int[] init(int [] ar,int lenght,int val){
    ar= new int[lenght];
    for(int i1=0,i=1;i<=ar.length+1;i1++,i++){
        if(i==val) {
            i1--;
            val=0;
            continue;
        }
        ar[i1]=i;
    }
    return ar;
}
public static int searchBin(int[] ar){
    int start=ar[0];//1
    int end=ar[ar.length-1];//100
    int sum=start+end;//101
    int r=sum;//101
    while(r==sum){//true
        start++;//2
        end--;//99
        start= ar[start-1];//2
        end  = ar[end-2];// поставил -2 вместо -1
        r=start+end;//101
    }
    return start-1; // поставил -1
}
Answer 3

Есть предположение что в строке:

end--;

нужно использовать префиксную форму, поскольку мы хотим использовать значение сразу.

READ ALSO
Как работает if и else?

Как работает if и else?

В приложении есть чекбокс, и если пользователь устанавливает галочку то мы должны считать цену чашки кофе не по 5$, а по 6$

212
Получить путь директории Tomcat

Получить путь директории Tomcat

подскажите пожалуйста, может кто знаетМожно ли как-то в java получить корневой путь Томката?

131
Обработчик ошибок для части кода

Обработчик ошибок для части кода

Код, который должен быть в обработчике ошибок:

146