Searching: linear and binary

English

Finding a value

A common job is to search: is a value in an array, and where?
The usual answer is the index where we found it, or -1 if it is not there.
We learn two ways: linear search (works on any array) and binary search (needs a sorted array, but is much faster).

Русский

Поиск значения

Частая задача — поиск: есть ли значение в массиве и где именно?
Обычный ответ — индекс, где оно было найдено, или -1, если его нет.
Мы изучаем два способа: линейный поиск (работает с любым массивом) и бинарный поиск (требует отсортированного массива, но работает значительно быстрее).

English

Linear search

Look at each item from index 0 to the end.
If the item equals the target, return its index right away.
If the loop finishes with no match, return -1.

Русский

Линейный поиск

Просмотрите каждый элемент от индекса 0 до конца.
Если элемент равен целевому, верните его индекс немедленно.
Если цикл завершился без совпадений, верните -1.

public class Main {
    public static void main(String[] args) {
        int[] a = {4, 8, 15, 16, 23};
        int target = 15;
        int found = -1;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target) {
                found = i;
                break;       // stop early, we have it
            }
        }
        System.out.println(found);   // 2
    }
}

English

How fast is linear search?

In the worst case (the value is last, or missing) it checks every item.
For a list of n items that is up to n checks. We call this linear time.
For small arrays this is totally fine. For huge sorted arrays we can do better.

Русский

Как быстро работает линейный поиск?

В худшем случае (значение находится последним или отсутствует) он проверяет каждый элемент.
Для списка из n элементов это составляет до n проверок. Мы называем это линейным временем.
Для малых массивов это вполне приемлемо. Для огромных отсортированных массивов можно сделать лучше.

English

Binary search needs a sorted array

Binary search only works when the array is already sorted (small to large).
It checks the middle item, then throws away half the array each step.
That is much faster: a million items take about 20 checks, not a million.

Русский

Бинарному поиску нужен отсортированный массив

Бинарный поиск работает только тогда, когда массив уже отсортирован (по возрастанию).
Он проверяет средний элемент, а на каждом шаге отбрасывает половину массива.
Это намного быстрее: миллион элементов требует около 20 проверок, а не миллион.

English

The binary search idea

Keep two bounds: low (start) and high (end).
Look at the middle index mid = (low + high) / 2.
If a[mid] equals the target, return mid.
If a[mid] is too small, the target must be on the right, so set low = mid + 1.
If a[mid] is too big, the target must be on the left, so set high = mid - 1.
Stop when low passes high; then the value is not there, return -1.

Русский

Идея бинарного поиска

Держите две границы: low (начало) и high (конец).
Посмотрите на средний индекс mid = (low + high) / 2.
Если ⟨a[mid]⟩ равно целевому значению, верните ⟨mid⟩.
Если ⟨a[mid]⟩ слишком мало, целевое значение должно быть справа, поэтому установите ⟨low = mid + 1⟩.
Если ⟨a[mid]⟩ слишком велико, целевое значение должно быть слева, поэтому установите ⟨high = mid - 1⟩.
Остановитесь, когда ⟨low⟩ превысит ⟨high⟩; тогда значения нет, верните ⟨-1⟩.

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12, 16, 23, 38};   // sorted!
        int target = 16;

        int low = 0;
        int high = a.length - 1;
        int found = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                found = mid;
                break;
            } else if (a[mid] < target) {
                low = mid + 1;     // go right
            } else {
                high = mid - 1;    // go left
            }
        }
        System.out.println(found);   // 4
    }
}

English

When a value is missing

Both searches return -1 when the target is not in the array.
For binary search, the loop ends when low > high — the bounds have crossed, so there is nowhere left to look.
Always handle the -1 case in code that calls a search.

Русский

Когда значение отсутствует

Оба поиска возвращают ⟨-1⟩, когда целевое значение отсутствует в массиве.
Для бинарного поиска цикл завершается, когда low > high — границы пересеклись, и искать больше негде.
Всегда обрабатывайте случай -1 в коде, вызывающем поиск.

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12};   // sorted
        int target = 7;            // not in the array

        int low = 0;
        int high = a.length - 1;
        int found = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                found = mid;
                break;
            } else if (a[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        System.out.println(found);   // -1
    }
}

English

Common mistakes

Binary search needs a sorted array.
Linear search is O(n); binary is O(log n).

Русский

Распространенные ошибки

Бинарному поиску нужен отсортированный массив.
Линейный поиск — O(n); бинарный — O(log n).

English

Now you try

Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
Press Run to compile and run, then Check answer.
Your code compiles and runs on the server, so even the first run is fast.

Русский

Теперь попробуйте сами

Каждая задача заранее заполняет каркас класса — напишите свой код внутри main или дополните показанный метод.
Нажмите Run (Выполнить), чтобы скомпилировать и запустить, затем Check answer (Проверить ответ).
Ваш код компилируется и выполняется на сервере, поэтому даже первый запуск происходит быстро.

Explore · ⁨Исследовать⁩

Linear vs binary search

Binary search halves the range each step — far fewer checks.

Complete linearSearch(int[] a, int target). Return the index of the first item equal to target, or -1 if it is not in the array. Check items from index 0 upward.

public class SearchUtil {
    // Return the index of target, or -1 if not found.
    public static int linearSearch(int[] a, int target) {
        return -1;   // change this
    }
}

Click Run to see the output here. · ⁨Нажмите Запустить, чтобы увидеть результат здесь.⁩

Complete binarySearch(int[] a, int target) for a sorted array. Use low/high bounds and check the middle each step. Return the index of target, or -1 if it is missing.

public class SearchUtil {
    // Binary search on a sorted array. Return index or -1.
    public static int binarySearch(int[] a, int target) {
        int low = 0;
        int high = a.length - 1;
        // your loop here
        return -1;
    }
}

Click Run to see the output here. · ⁨Нажмите Запустить, чтобы увидеть результат здесь.⁩

Complete countOccurrences(int[] a, int target) that returns how many times target appears in a (a linear scan). Return 0 if it never appears.

public class SearchUtil {
    // Count how many times target appears in a.
    public static int countOccurrences(int[] a, int target) {
        return 0;   // change this
    }
}

Click Run to see the output here. · ⁨Нажмите Запустить, чтобы увидеть результат здесь.⁩

Finding a value

Поиск значения

Linear search

Линейный поиск

How fast is linear search?

Как быстро работает линейный поиск?

Binary search needs a sorted array

Бинарному поиску нужен отсортированный массив

The binary search idea

Идея бинарного поиска

When a value is missing

Когда значение отсутствует

Common mistakes

Распространенные ошибки

Now you try

Теперь попробуйте сами

Linear vs binary search

Handout · ⁨Раздаточный материал⁩

Log in or create account · ⁨Войти или создать аккаунт⁩

Your subject · ⁨Ваш предмет⁩

All sections · ⁨Все разделы⁩

Feedback & help · ⁨Обратная связь и помощь⁩