Реализация бинарного поиска на Java

public class BinSearch {

    public static Object binSearch(ArrayList<Integer> list, int item) {
        int low = 0; // нижняя граница списка
        int high = list.size() - 1; // верхняя граница списка

        while (low <= high) { // пока эта част не сократится до одного элемента
            int mid = (low + high) / 2; // проверяем средний элемент
            int guess = list.get(mid);
            if (guess == item) { // если значение найдено
                return mid;
            }
            if (guess > item) { // много
                high = mid - 1;
            }
            else { // мало
                low = mid + 1;
            }
        }
        return null; // значение не существует
    }

    public static void binSearchStart() {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(3);
        list.add(5);
        list.add(7);
        list.add(9);

        System.out.println(binSearch(list, 3));
        System.out.println(binSearch(list, -1));
    }

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

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

Добавить комментарий