0Pricing
Go Academy · Урок

Поиск в отсортированных данных

Выполняйте двоичный поиск

«Поиск в отсортированных данных» — бесплатный урок Go Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Go Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Go Academy содержит 4 уроков всего.

Зачем искать в отсортированных данных

После сортировки среза можно находить элементы значительно быстрее с помощью двоичного поиска, не просматривая каждый элемент.

Пакет Go sort предоставляет вспомогательные функции поиска, работающие за логарифмическое время.

Линейный и двоичный поиск

Линейный поиск проверяет элементы один за другим (O(n)). Двоичный поиск на каждом шаге вдвое сокращает диапазон поиска (O(log n)), но сначала требует, чтобы данные были отсортированы.

sort.SearchInts

sort.SearchInts находит индекс, по которому находится значение, или индекс, куда его можно вставить, чтобы срез оставался отсортированным. Срез уже должен быть отсортирован по возрастанию.

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{1, 3, 5, 7, 9}
	i := sort.SearchInts(nums, 5)
	fmt.Println("index:", i)
}

Подтверждение совпадения

SearchInts возвращает индекс, даже если значение отсутствует (позицию вставки). Всегда подтверждайте результат, проверяя i < len(s) && s[i] == target.

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{1, 3, 5, 7}
	target := 4
	i := sort.SearchInts(nums, target)
	found := i < len(nums) && nums[i] == target
	fmt.Println("index:", i, "found:", found)
}

Позиция вставки

Если значение отсутствует, возвращённый индекс точно указывает, куда его нужно вставить, чтобы сохранить сортировку. Здесь число 4 должно находиться по индексу 2.

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{1, 3, 5, 7}
	i := sort.SearchInts(nums, 4)
	fmt.Println("insert 4 at index:", i)
}

SearchStrings

sort.SearchStrings выполняет то же самое для отсортированного среза строк.

package main

import (
	"fmt"
	"sort"
)

func main() {
	words := []string{"apple", "cherry", "mango"}
	i := sort.SearchStrings(words, "cherry")
	fmt.Println("index:", i)
}

Общий поиск с помощью sort.Search

sort.Search — гибкая основа поиска. Вы передаёте ей длину и функцию f, которая сначала возвращает false, а затем true; функция возвращает наименьший индекс, для которого f равна true.

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{2, 4, 6, 8, 10}
	i := sort.Search(len(nums), func(i int) bool {
		return nums[i] >= 6
	})
	fmt.Println("first >= 6 at index:", i)
}

Поиск первого элемента больше заданного

Поскольку sort.Search находит границу, в которой условие меняется на истинное, он отлично подходит для запросов вроде поиска первого значения, превышающего порог.

package main

import (
	"fmt"
	"sort"
)

func main() {
	scores := []int{10, 20, 30, 40}
	i := sort.Search(len(scores), func(i int) bool {
		return scores[i] > 25
	})
	fmt.Println("first > 25:", scores[i])
}

Сначала необходимо отсортировать

Двоичный поиск предполагает наличие порядка. Если срез не отсортирован, результаты бессмысленны. Всегда сортируйте данные перед поиском.

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{9, 1, 5, 3}
	sort.Ints(nums)
	i := sort.SearchInts(nums, 5)
	fmt.Println(nums, "-> index of 5:", i)
}

Выигрыш в производительности

Для среза из миллиона элементов линейный поиск может проверить миллион элементов, а двоичный — около 20. Затраты на однократную сортировку окупаются при многочисленных поисках.

Выбор вспомогательной функции поиска

Итоги:

  • sort.SearchInts / SearchStrings / SearchFloat64s — типизированные срезы
  • sort.Search — собственное условие для любых данных, поддерживающих индексацию

Быстрая проверка

Вы вызываете sort.SearchInts(s, 4) для отсортированного среза, который не содержит число 4. Что будет возвращено?

Итоги

Поиск в отсортированных данных с помощью двоичного поиска:

  • Сначала данные должны быть отсортированы
  • Вспомогательные функции возвращают индекс или позицию вставки
  • Подтверждайте совпадения проверкой на равенство
  • sort.Search обрабатывает собственные условия

Часто задаваемые вопросы

Урок «Поиск в отсортированных данных» бесплатный?

Да — полный текст урока «Поиск в отсортированных данных» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Go Academy, подпишись на CoddyKit PRO. Курс Go Academy содержит 4 уроков всего.

Чему я научусь в уроке «Поиск в отсортированных данных»?

Выполняйте двоичный поиск Ты практикуешь Go Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Go Academy?

Предыдущий опыт не требуется. Go Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Поиск в отсортированных данных»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Go Academy?

Да. Каждый урок Go Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Сортировка срезов
  2. Пользовательский порядок сортировки
  3. Поиск в отсортированных данных
  4. Стабильная сортировка
← Назад к Go Academy