Бинарный поиск

Бинарный поиск

Суть алгоритма

Бинарный поиск — это быстрый алгоритм поиска элемента в отсортированном массиве за O(log n). Работает по принципу деления промежутка пополам.

Как работает

1. Устанавливаем левую границу left = 0 и правую границу right = length - 1
2. Находим средний элемент mid = (left + right) / 2
3. Сравниваем элемент в позиции mid с target:
   • Если равны — найден!
   • Если nums[mid] < target — ищем в правой половине (left = mid + 1)
   • Если nums[mid] > target — ищем в левой половине (right = mid - 1)
4. Повторяем, пока left <= right

Итеративная реализация

public int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;  // пустой массив
    }
    
    int left = 0;
    int right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // избегаем переполнения
        
        if (nums[mid] == target) {
            return mid;  // найдено!
        } else if (nums[mid] < target) {
            left = mid + 1;  // ищем в правой половине
        } else {
            right = mid - 1;  // ищем в левой половине
        }
    }
    
    return -1;  // не найдено
}

Рекурсивная реализация

public int binarySearchRecursive(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;  // пустой массив
    }
    return binarySearchHelper(nums, target, 0, nums.length - 1);
}

private int binarySearchHelper(int[] nums, int target, int left, int right) {
    if (left > right) {
        return -1;  // базовый случай: не найдено
    }
    
    int mid = left + (right - left) / 2;
    
    if (nums[mid] == target) {
        return mid;  // найдено!
    } else if (nums[mid] < target) {
        return binarySearchHelper(nums, target, mid + 1, right);
    } else {
        return binarySearchHelper(nums, target, left, mid - 1);
    }
}

Пошаговый пример

nums = [-1, 0, 3, 5, 9, 12], target = 9

Шаг 1: left=0, right=5, mid=2
  nums[2]=3 < 9 → left=3

Шаг 2: left=3, right=5, mid=4
  nums[4]=9 == 9 ✓ НАЙДЕНО!
  Ответ: 4

Пример 2: target = 2
Шаг 1: left=0, right=5, mid=2
  nums[2]=3 > 2 → right=1

Шаг 2: left=0, right=1, mid=0
  nums[0]=-1 < 2 → left=1

Шаг 3: left=1, right=1, mid=1
  nums[1]=0 < 2 → left=2

Шаг 4: left=2, right=1
  left > right → НЕ НАЙДЕНО
  Ответ: -1

Важный момент: избегаем переполнения

// ❌ Неправильно — может быть переполнение
int mid = (left + right) / 2;

// ✓ Правильно — без переполнения
int mid = left + (right - left) / 2;

При больших значениях left и right их сумма может выйти за границы int.

Обработка граничных случаев

public int binarySearch(int[] nums, int target) {
    // Пустой массив
    if (nums == null || nums.length == 0) {
        return -1;
    }
    
    // Элемент меньше минимума
    if (target < nums[0]) {
        return -1;
    }
    
    // Элемент больше максимума
    if (target > nums[nums.length - 1]) {
        return -1;
    }
    
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    return -1;
}

Тесты

public class BinarySearchTest {
    private BinarySearch solution = new BinarySearch();
    
    @Test
    public void testBasic() {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        assertEquals(4, solution.binarySearch(nums, 9));
    }
    
    @Test
    public void testNotFound() {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        assertEquals(-1, solution.binarySearch(nums, 2));
    }
    
    @Test
    public void testSingleElement() {
        int[] nums = {5};
        assertEquals(0, solution.binarySearch(nums, 5));
    }
    
    @Test
    public void testEmpty() {
        int[] nums = {};
        assertEquals(-1, solution.binarySearch(nums, 5));
    }
    
    @Test
    public void testNull() {
        assertEquals(-1, solution.binarySearch(null, 5));
    }
    
    @Test
    public void testFirstElement() {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        assertEquals(0, solution.binarySearch(nums, -1));
    }
    
    @Test
    public void testLastElement() {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        assertEquals(5, solution.binarySearch(nums, 12));
    }
    
    @Test
    public void testRecursive() {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        assertEquals(4, solution.binarySearchRecursive(nums, 9));
    }
}

Сравнение итеративной и рекурсивной версий

Сложность

• Временная: O(log n) — каждая итерация уменьшает область поиска в 2 раза
• Пространственная: O(1) для итеративной, O(log n) для рекурсивной (stack)

Практическое применение

• Поиск в большых отсортированных списках
• Нахождение позиции для вставки элемента
• Поиск первого/последнего вхождения
• Поиск в диапазонах

Вывод

Бинарный поиск — основной алгоритм, который нужно знать наизусть. Итеративная версия предпочтительнее из-за лучшей производительности и отсутствия риска переполнения стека. Помните о правильном вычислении mid для избежания переполнения!