Упражнения по Go

Binary Search in Go

Find a value in a sorted slice by halving the search range at every step.

Начальный
Чтение: 3 мин
Примеров для запуска: 1

Что вы узнаете

low, high and middle
Returning -1 when missing
Why it is fast

Запустить код →

Search for 23

164

235

386

567

Found at index 5 after three steps.

Halve the range each step

Binary search looks at the middle of a sorted list and throws away the half that cannot contain the target. Each step halves the work, so it is very fast on large lists.

low and high mark the part that is still being searched. The function returns the position of the target, or -1 when the range becomes empty. low + (high-low)/2 finds the middle without overflow.

Главное

The slice must be sorted.
Each step throws away half.
-1 means the value is not there.

Пример на Go, который можно запустить

Запустить код →

main.go

package main

import "fmt"

func binarySearch(items []int, target int) int {
	low, high := 0, len(items)
	for low < high {
		middle := low + (high-low)/2
		switch {
		case items[middle] == target:
			return middle
		case items[middle] < target:
			low = middle + 1
		default:
			high = middle
		}
	}
	return -1
}

func main() {
	sorted := []int{2, 5, 8, 12, 16, 23, 38, 56}
	fmt.Println(binarySearch(sorted, 23))
	fmt.Println(binarySearch(sorted, 7))
}

Получить кнопку запуска для этого примера Результат выполнения

5
-1

Практика

Откройте пример в онлайн-компиляторе, измените значение или добавьте строку и попробуйте предсказать вывод до запуска. Затем намеренно сломайте код и прочитайте сообщение компилятора.

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Далее: Bank Account with Errors →

Попрактикуйтесь на задаче

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

Все задачи