Объясните механизм работы алгоритма двоичного поиска и как он выполняется на практике

Двоичный поиск — это алгоритм поиска элемента в отсортированном массиве, который работает за логарифмическое время O(log n).

Принцип работы:

1. Определяем середину массива.
2. Сравниваем искомое значение с элементом в середине.
3. Если значения совпадают — возвращаем индекс.
4. Если искомое значение меньше, ищем в левой половине массива.
5. Если больше — в правой половине.
6. Повторяем процесс рекурсивно или итеративно, пока не найдём элемент или не останется элементов для поиска.

Пример на Java:

public int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // элемент не найден
}

Важно, чтобы массив был отсортирован, иначе алгоритм не гарантирует корректный результат.