Untitled

 avatar
unknown
plain_text
2 years ago
3.2 kB
91
Indexable
public class Practicum {

   public static void main(String[] args) {
        int[] arrayAsc = {1, 2, 5, 8, 12, 13, 20, 22, 24, 30, 32};

        int[] arrayDesc = {32, 30, 24, 22, 20, 13, 12,  8,  5,  2, 1};

        System.out.println("Индекс искомого элемента: " + searchBinaryAscending(arrayAsc, 30));
        System.out.println("Индекс искомого элемента: " + searchBinaryDescending(arrayDesc, 30));
        System.out.println("Индекс искомого элемента: " + searchBinary(arrayAsc, 30));
        System.out.println("Индекс искомого элемента: " + searchBinary(arrayDesc, 30));
    }

    private static int searchBinaryDescending(int[] array, int elem) {
        // изначально мы запускаем двоичный поиск на всей длине массива
        return searchBinaryRecursiveDescending(array, elem, 0, array.length - 1);
    }

    private static int searchBinaryAscending(int[] array, int elem) {
        // изначально мы запускаем двоичный поиск на всей длине массива
        return searchBinaryDescending(array, elem);
    }

    private static int searchBinaryRecursiveDescending(int[] array, int elem, int low, int high) {
        if(high <= low) { // промежуток пуст
            return -1;
        }
        // промежуток не пуст
        int mid = low  + ((high - low) / 2);
        if (array[mid] == elem) { // центральный элемент — искомый
            return mid;
        } else if(elem < array[mid]){ // на этот раз искомый элемент больше центрального
            // все элементы больше центрального и располагаются в левой половине
            return searchBinaryRecursiveDescending(array, elem, mid + 1, high);
        } else { // иначе следует искать в правой половине
            return searchBinaryRecursiveDescending(array, elem, low, mid);
        }
    }

    private static int searchBinary(int[] array, int elem) {
        // возвращает 1, если массив отсортирован по возрастанию, и -1, если по убыванию
        int sort = getSortRecursive(array, 0, 0);
       if(sort > 0){
            return  searchBinaryAscending(array, elem);
        } else if (sort < 0){
            return searchBinaryDescending(array, elem);
        } else {
            return -1;
        }

    }

    private static int getSortRecursive(int[] array, int sort, int next) {
        // рекурсивно сравните каждый следующий элемент с предыдущим
        if (next == array.length-1) {
            return sort;
        }
        if (array[next] < array[next +1]) {
            if (sort == -1) {
                return 0;
            }
            return getSortRecursive(array, 1, next+1);
        } else {
            if (sort == 1) {
                return 0;
            }
            return getSortRecursive(array, - 1, next+1);
        }
    }
}
Editor is loading...