Реализовать бинарный поиск

Решение

Бинарный поиск — это фундаментальный алгоритм поиска в отсортированном массиве. Основная идея: разделить пространство поиска пополам на каждой итерации.

Подход

1. Инициализируем два указателя: left = 0, right = len(arr) - 1
2. Пока left <= right:
   • Вычисляем середину: mid = (left + right) / 2
   • Если arr[mid] == target → возвращаем mid
   • Если arr[mid] < target → ищем в правой половине (left = mid + 1)
   • Если arr[mid] > target → ищем в левой половине (right = mid - 1)
3. Если цикл завершился, элемент не найден → возвращаем -1

Реализация

func binarySearch(arr []int, target int) int {
    left := 0
    right := len(arr) - 1
    
    for left <= right {
        // Вычисляем середину (предотвращаем переполнение)
        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  // элемент не найден
}

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

Задача: найти 55 в массиве [1, 3, 4, 6, 8, 10, 55, 56, 59, 70, 79, 81, 91, 10001]

Индексы: 0  1  2  3  4  5   6   7   8   9  10  11  12    13
Массив: [1, 3, 4, 6, 8, 10, 55, 56, 59, 70, 79, 81, 91, 10001]

Итерация 1:
  left=0, right=13
  mid = 0 + (13-0)/2 = 6
  arr[6] = 55, target = 55
  → найдено! вернуть 6

Задача: найти 5 в массиве [1, 3, 4, 6, 8, 10]

Индексы: 0  1  2  3  4  5
Массив: [1, 3, 4, 6, 8, 10]

Итерация 1:
  left=0, right=5
  mid = 0 + (5-0)/2 = 2
  arr[2] = 4, target = 5
  4 < 5 → left = 3

Итерация 2:
  left=3, right=5
  mid = 3 + (5-3)/2 = 4
  arr[4] = 8, target = 5
  8 > 5 → right = 3

Итерация 3:
  left=3, right=3
  mid = 3 + (3-3)/2 = 3
  arr[3] = 6, target = 5
  6 > 5 → right = 2

Итерация 4:
  left=3, right=2
  left > right → выходим из цикла
  → вернуть -1 (не найдено)

Анализ сложности

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

Сравнение с линейным поиском:

• Линейный поиск: O(n) — для массива из 1 млн элементов потребуется до 1 млн проверок
• Бинарный поиск: O(log n) ≈ 20 проверок для 1 млн элементов

Важная оптимизация: вычисление mid

❌ Неправильно (может быть переполнение):

mid := (left + right) / 2
// Если left и right близки к максимальному int, sum переполнится

✅ Правильно (безопасно):

mid := left + (right-left)/2
// Эквивалентно (left + right) / 2, но без переполнения

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

func binarySearch(arr []int, target int) int {
    return binarySearchHelper(arr, target, 0, len(arr)-1)
}

func binarySearchHelper(arr []int, target int, left, right int) int {
    if left > right {
        return -1
    }
    
    mid := left + (right-left)/2
    
    if arr[mid] == target {
        return mid
    } else if arr[mid] < target {
        return binarySearchHelper(arr, target, mid+1, right)
    } else {
        return binarySearchHelper(arr, target, left, mid-1)
    }
}

Использование встроенной функции Go

Go имеет встроенный бинарный поиск в пакете sort:

import "sort"

func binarySearch(arr []int, target int) int {
    // SearchInts возвращает индекс вставки, который может быть len(arr)
    idx := sort.SearchInts(arr, target)
    if idx < len(arr) && arr[idx] == target {
        return idx
    }
    return -1
}

Полный код с примерами

package main

import "fmt"

func binarySearch(arr []int, target int) int {
    left := 0
    right := len(arr) - 1
    
    for left <= right {
        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
}

func main() {
    // Пример 1
    arr1 := []int{1, 3, 4, 6, 8, 10, 55, 56, 59, 70, 79, 81, 91, 10001}
    fmt.Println(binarySearch(arr1, 55))   // 6
    
    // Пример 2
    arr2 := []int{1, 3, 4, 6, 8, 10}
    fmt.Println(binarySearch(arr2, 5))    // -1
    
    // Пример 3
    arr3 := []int{1, 2, 3, 4, 5}
    fmt.Println(binarySearch(arr3, 1))    // 0 (первый элемент)
    fmt.Println(binarySearch(arr3, 5))    // 4 (последний элемент)
    fmt.Println(binarySearch(arr3, 3))    // 2 (средний)
}

Особые случаи

1. Пустой массив

binarySearch([]int{}, 5)  // -1

2. Один элемент

binarySearch([]int{5}, 5)  // 0
binarySearch([]int{5}, 3)  // -1

3. Дубликаты Стандартный бинарный поиск вернёт любой индекс дубликата (не обязательно первый). Если нужен первый или последний дубликат, нужна модификация:

// Найти ПЕРВОЕ вхождение
func binarySearchFirst(arr []int, target int) int {
    left, right := 0, len(arr)-1
    result := -1
    
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            result = mid
            right = mid - 1  // ← продолжаем искать влево
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return result
}

Ключевые выводы

1. Бинарный поиск требует отсортированный массив
2. Сложность O(log n) — очень эффективно для больших данных
3. Проверять left <= right, а не left < right
4. Вычисление mid: mid = left + (right-left)/2
5. Базовый случай: left > right → элемент не найден

Этот алгоритм — основа для множества advanced структур (BST, segment trees, и т.д.)