Към съдържанието
wannacode

Двоично търсене

Накратко: Двоичното търсене намира стойност в подреден масив, като сравнява със средата и всеки път изхвърля половината: O(log n) сравнения.

Проблем

Филтърът, който чете целия каталог

Магазинът има 1 000 000 продукта, а ценоразписът е подреден по цена. Филтърът „точна цена“ търси с цикъл от началото, като линейното търсене. Цените в кода са в евроцентове: от 2 до 2 000 000. Клиент търси продукт за 20 000,01 €, а такъв няма:

int n = 1_000_000;
int[] prices = new int[n];
for (int i = 0; i < n; i++) {
    prices[i] = 2 * (i + 1);
}
int target = 2 * n + 1;


int comparisons = 0;
int found = -1;
for (int i = 0; i < n; i++) {
    comparisons++;
    if (prices[i] == target) {
        found = i;
        break;
    }
}
System.out.println("Индекс: " + found);
System.out.println("Сравнения: " + comparisons);
Изход
Индекс: -1
Сравнения: 1000000

Милион сравнения, за да кажеш „няма“. А при всяко отваряне на страницата филтърът се пуска за десетки цени.

Цените са подредени, а цикълът не се възползва от това. Когато търсиш дума в речник, не четеш от първата страница. Отваряш по средата и гледаш дали думата е преди или след.

Идеята

Питай средата, изхвърли половината

Погледни цената по средата на ценоразписа:

  • ако е търсената, готово;
  • ако е по-малка, търсената може да е само вдясно. Лявата половина отпада, заедно със средата;
  • ако е по-голяма, търсената може да е само вляво.

После същото с половината, която остава. Това е двоично търсене (binary search). Обхватът, в който цената още може да е, се пази с два индекса: lo (началото) и hi (краят). Средата е mid.

Всяко сравнение разполовява обхвата. 1 000 000 цени стават 500 000, после 250 000, и след около 20 деления остава една. Колко пъти делиш на 2, докато стигнеш до 1, се казва логаритъм при основа 2: log₂ 1 000 000 ≈ 20. Затова двоичното търсене е O(log n), а линейното е O(n).

Условието е едно: масивът трябва да е подреден. В неподреден масив „по-малка е, значи е вдясно“ не е вярно.

Виж го

lo, mid и hi в ценоразписа

static int find(int[] prices, int target) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] == target) {
            return mid;
        } else if (prices[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}
int[] prices = {3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58};
System.out.println("Индекс: " + find(prices, 49));
Изход
Индекс: 12

static int find(int[] prices, int target) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] == target) {
            return mid;
        } else if (prices[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}
Стъпка по стъпка, с думи
  1. Ценоразписът е подреден: 15 цени. Търсим 49 €. lo и hi обхващат всичко, от 0 до 14.
  2. mid = 7: 27 € < 49 €, значи цената е вдясно. lo = 8, лявата част отпада. Остават 7 цени.
  3. mid = 11: 44 € < 49 €, значи цената е вдясно. lo = 12, лявата част отпада. Остават 3 цени.
  4. mid = 13: 53 € > 49 €, значи цената е вляво. hi = 12, дясната част отпада. Остава 1 цена.
  5. mid = 12: 49 €. Това е търсената цена: find връща 12.
  6. 4 сравнения. Търсене от началото би погледнало 13 цени, а за 1 000 000 цени двоичното търсене иска най-много 20.
Средата е lo + (hi - lo) / 2, а не (lo + hi) / 2. Двете дават едно и също число, но второто може да прелее. Защо, е на една от следващите карти.
По-точно, за любопитните

Най-лошият случай е, когато цената я няма: обхватът се дели, докато lo не мине hi. За n цени това са най-много ⌊log₂ n⌋ + 1 сравнения: 4 за 10 цени, 10 за 1000, 20 за 1 000 000. Най-добрият случай е едно сравнение: цената е точно на средата.

Тук „сравнение“ е една проба на mid. Проверката за равно и за по-малко са два реда в кода, но питат за една и съща цена.

Пробвай

Предвиди колко проби

Подредени цени в евроцентове: 2, 4, 6, …, 2000. Търси се 2001, а такава цена няма. Колко пъти минава цикълът?

int n = 1000;
int[] prices = new int[n];
for (int i = 0; i < n; i++) {
    prices[i] = 2 * (i + 1);
}
int target = 2 * n + 1;


int steps = 0;
int lo = 0;
int hi = n - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    steps++;
    if (prices[mid] == target) {
        break;
    } else if (prices[mid] < target) {
        lo = mid + 1;
    } else {
        hi = mid - 1;
    }
}
System.out.println(steps);
Отговор

Пробвай

Попълни

Цената на mid е по-малка от търсената. Откъде започва новият обхват?

static int find(int[] prices, int target) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] == target) {
            return mid;
        } else if (prices[mid] < target) {
            lo = ;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

Идеята

Границите: къде греши всеки

Двоичното търсене се пише в шест реда, а е известно с това, че се пише грешно. Грешката почти винаги е с едно: < вместо <=, mid вместо mid - 1. Казва се off-by-one (грешка с единица).

Пазиш я с едно решение: какво значат lo и hi, и после го спазваш навсякъде.

  • Затворен обхват [lo, hi]: и двата края може да са цената. hi започва от последния индекс, цикълът е докато lo <= hi, а изхвърлената среда е hi = mid - 1 и lo = mid + 1. Това е find от горе.
  • Полуотворен обхват [lo, hi): hi е първото място след обхвата. hi започва от дължината на масива, цикълът е докато lo < hi, а наляво се отива с hi = mid, защото hi така и така не е в обхвата.

Двете са верни. Грешката е, когато ги смесиш. Ето затворен обхват с hi = mid от полуотворения. Търси се 4 €, а такава цена няма. Ограничителят спира цикъла след 8 проби, иначе нямаше да спре:

static int find(int[] prices, int target) {
    int lo = 0;
    int hi = prices.length - 1;
    int probes = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        System.out.println("lo=" + lo + " hi=" + hi + " mid=" + mid);
        if (++probes == 8) {
            System.out.println("Спирам след 8 проби: lo и hi не мърдат");
            return -1;
        }
        if (prices[mid] == target) {
            return mid;
        } else if (prices[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return -1;
}
int[] prices = {3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58};
find(prices, 4);
Изход
lo=0 hi=14 mid=7
lo=0 hi=7 mid=3
lo=0 hi=3 mid=1
lo=0 hi=1 mid=0
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
Спирам след 8 проби: lo и hi не мърдат

Когато lo и hi станат 1, средата е 1, цената там е 5 €, повече от 4 €, и hi = mid пак е 1. Нищо не се сменя. Това е безкраен цикъл: програмата не пада, само виси.

Пробвай

Намери грешката

Търсенето намира 49 €, но не намира най-скъпия продукт, 58 €, макар че той е в ценоразписа:

int[] prices = {3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58};
System.out.println("Индекс: " + find(prices, 58));
Изход
Индекс: -1

Избери реда с грешката.

Идеята

Когато (lo + hi) / 2 прелива

int в Java стига до 2 147 483 647. Масив с повече от милиард елемента е рядък, но го има: индекс на файл, лог, база в паметта. Тогава lo + hi може да мине границата:

int lo = 1_500_000_000;
int hi = 2_000_000_000;
System.out.println((lo + hi) / 2);
System.out.println(lo + (hi - lo) / 2);
System.out.println((lo + hi) >>> 1);
Изход
-397483648
1750000000
1750000000

Сборът е 3 500 000 000. Той не се побира в int и Java не дава грешка, а го обръща в отрицателно число: средата става -397 483 648, а индекс -397 483 648 хвърля изключение. lo + (hi - lo) / 2 смята същото, без да събира: разликата винаги се побира. (lo + hi) >>> 1 е другият начин: >>> мести битовете надясно, като гледа на числото като на неотрицателно, а това е делене на 2.

По-точно, за любопитните

Грешката не е измислена. Двоичното търсене в стандартната библиотека на Java, Arrays.binarySearch, е имало (low + high) / 2 девет години. Джошуа Блох го описва през 2006 г. в статията „Nearly All Binary Searches and Mergesorts are Broken“: програма с масив от повече от 2³⁰ елемента пада с ArrayIndexOutOfBoundsException. Днес там пише (low + high) >>> 1.

Виж го

Първата цена от 20 € нагоре

Филтърът „цена от 20 €“ не търси точна цена. Търси първото място, където цената е поне 20 €: от него нататък са всички продукти, които трябва да покаже. Това се казва долна граница (lower bound). Тя е и първото срещане: ако цените имат три продукта по 15 €, долната граница на 15 е първият от тях.

find не я дава: той спира на първото 15, на което стъпи. Долната граница е с полуотворен обхват, и цикълът не спира при равно, а продължава наляво:

static int lowerBound(int[] prices, int target) {
    int lo = 0;
    int hi = prices.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}
int[] prices = {3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49};
System.out.println("find: " + find(prices, 15));
int first = lowerBound(prices, 15);
System.out.println("Първото 15 €: индекс " + first);
System.out.println("Продукти по 15 €: " + (lowerBound(prices, 16) - first));
int from20 = lowerBound(prices, 20);
System.out.println("Първата цена от 20 € нагоре: " + prices[from20] + " €");
Изход
find: 5
Първото 15 €: индекс 4
Продукти по 15 €: 3
Първата цена от 20 € нагоре: 24 €

Ако цената е по-малка от търсената, тя и всичко преди нея отпадат: lo = mid + 1. Иначе mid може да е отговорът, затова остава в обхвата: hi = mid. Цикълът свършва, когато lo и hi се срещнат, а там е първото място с цена ≥ търсената. Ако такова няма, lo е дължината на масива. Колко продукта са по 15 €, е разликата между две долни граници: на 16 и на 15.

Java има готово двоично търсене: Arrays.binarySearch за масив и Collections.binarySearch за подреден List. Когато цената я няма, връща -(мястото, където би влязла) - 1, така че отрицателното число казва и къде е мястото:

int[] prices = {3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49};
System.out.println(Arrays.binarySearch(prices, 24));
int i = Arrays.binarySearch(prices, 20);
System.out.println(i);
System.out.println(-i - 1);
System.out.println(Arrays.binarySearch(prices, 15));
Изход
8
-9
8
5

С повторения Arrays.binarySearch връща едно от равните, без да обещава кое: за 15 € дава 5, а първото е на 4. За долна граница пишеш свой метод, като lowerBound.

Виж го

Измери: линейно срещу двоично

Линейното и двоичното търсене в същия подреден ценоразпис, когато търсената цена я няма. Линейното сравнява всяка цена: n сравнения. Двоичното прави 20 сравнения при 1 000 000 цени:

  • Линейно търсене (всяка цена) O(n)
  • Двоично търсене O(log n)
Алгоритъмn = 10n = 1000n = 100 000n = 1 000 000
Линейно търсене (всяка цена)101000100 0001 000 000
Двоично търсене4101720
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
static int find(int[] prices, int target) {
    int lo = 0;
    int hi = prices.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] == target) {
            return mid;
        } else if (prices[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

Кривата на двоичното почти лежи: при 100 пъти повече цени тя се качва с около 7 сравнения. Затова двоичното търсене е навсякъде, където нещо е подредено: индексите в базите данни, git bisect, търсенето на версия, от която тестът пада.

Упражнение

Ценовият филтър: от 10 € до 30 €

Реши задачата в редактора си.

От 10 € до 30 €. Филтърът показва колко продукта има с цена от 10 € до 30 € включително. Ценоразписът е подреден: 3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44 и 49 €. Не обхождай целия масив: с две двоични търсения намери първото място с цена ≥ 10 € и първото с цена ≥ 31 €. Разликата е броят.

Изход
От 10 € до 30 €: 7 продукта

Още задачи

  • Последното срещане. Напиши upperBound: първото място с цена, по-голяма от търсената. Последният продукт по 15 € е на едно място преди него.
  • Свободен час за доставка. Свободните часове за доставка са подреден масив от минути от полунощ (540 е 9:00). Клиентът иска доставка не по-рано от 14:10. Намери първия свободен час или кажи, че няма.
  • Къде влиза новата цена. Нов продукт за 21 € трябва да влезе в ценоразписа, без той да спре да е подреден. Намери мястото с двоично търсене.

Тест

Провери се

1. Ценоразписът има 1 000 000 цени, подредени по големина. Най-много колко сравнения прави двоичното търсене?
2. Обхватът е затворен: hi започва от последния индекс. Кое условие на цикъла е вярно?
3. При while (lo <= hi) някой пише hi = mid вместо hi = mid - 1. Какво става?
4. Цените имат три продукта по 15 €. Кой търсиш, за да покажеш всички продукти „от 15 € нагоре“?
5. Списъкът с продукти не е подреден. Става ли двоично търсене?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·