Бинарный поиск на языке Go
Этим постом начинаю тему алгоритмов на языке Go. Алгоритмы касаются не только айтишников, программирования и всяких там «странных» гиков. Они повсюду вокруг нас. Это основа. Для начала, определимся с тем, что же такое этот алгоритм.
Посмотрим в Википедию:
Алгоритм (лат. algorithmi — от имени среднеазиатского математика Аль-Хорезми) — конечная совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи.
Если проще — это набор точных действий для эффективного решения задачи!
Почему бинарный поиск? Да потому что его чаще всего спрашивают на собеседованиях и с него удобно начинать.
Принцип работы бинарного поиска
Когда нужно искать что-то в массиве каких-то данных, первым естественным решением — хочется по очереди перебрать все элементы массива и найти искомое. Прекрасная мысль! Но что делать, если в массиве 280 000 элементов? Перебирать таким способом начнете Вы, а заканчивать будут Ваши прапрапрапраправнуки...может быть. Ну Вы поняли...) Это не эффективное решение. Ищем другое, а для начала давайте проясним, что же такое этот самый массив?
Снова обратимся к Википедии, раз уж начали с самого начала идти этим путем:
Массив — структура данных, хранящая набор значений (элементов массива) , идентифицируемых по индексу или набору индексов, принимающих целые (или приводимые к целым) значения из некоторого заданного непрерывного диапазона.
Простым языком, это последовательность данных какого-либо формата, элементы которой расположены друг за другом и имеют соответствующих индекс. Это важно!
Перебрать по очереди 10 элементов, как на рисунке выше — можно, но это же пустая трата времени. Вот здесь и поможет бинарный поиск.
Разделим массив на две половинки и посмотрим, в какой из них лежит искомый элемент. Затем сравним с тем значением, что лежит посередине. Возможно, искомый элемент и будет этой «серединкой». Но, чтобы сделать это, нужен отсортированный массив, иначе как мы будем искать элемент в этой каше?)
Главное правило бинарного поиска — он работает только с отсортированными данными!
Итак, делим массив пополам и определяем, в какой из половинок оказался тот элемент, который мы ищем. Для примера будем искать элемент data8 из массива на рисунке ниже.
Что у нас получается? 10 / 2 = 5. Берем элемент №5 по индексу в массиве и сравниваем данные из него с data8. В пятой ячейке лежит data5, значит data8 оказывается в правой отсеченной половине массива. Мы отбросили половину массива слева, убедившись, что в ней нет элемента, который мы ищем.
Повторяем процедуру. За основу берем правый кусок и делим его пополам:
Мы снова поделили диапазон пополам и начали сравнивать: и вот, data8 оказался прямо по центру, то есть при сравнении оказалось, что мы нашли элемент всего за два прохода! (Это сделано, конечно для примера.) На этом алгоритм может завершаться, вернув нам значение 8 как индекс элемента, который мы ищем!
Давайте все это закодируем на Go и добавим, для удобства, интерактивности.)
// Бинарный поиск
package main
import(
"fmt"
"sort"
"strconv"
)
// binarySearch — функция бинарного поиска в массиве из целых чисел
funcbinarySearch(arr []int, target int)(int,bool){
sort.Ints(arr)// первый шаг — сортировка массива
var mid int// середина
min :=0
high :=len(arr)-1
for min <= high {
mid =(min + high)/2
if mid == target {
return mid,true
}
if mid > target {
high = mid -1
} else {
min = mid +1
}
}
return0,false
}
funcmain(){
var numElem int
fmt.Println("Введите количество элементов массива:")
fmt.Scan(&numElem)
array :=make([]int, numElem)
fmt.Println("Создается массив...")
for i :=0; i < numElem; i++{
array[i]= i fmt.Print(strconv.Itoa(i)+" ")
}
fmt.Println()
var lookNum int
fmt.Println("Какой элемент будем искать?")
fmt.Scan(&lookNum)
nowNum, res :=binarySearch(array, lookNum)
if res {
fmt.Printf("Найден элемент: %v", strconv.Itoa(nowNum))
} else {
fmt.Println("Ничего не найдено.")
}
}
Получилось немного длинно, зато с комфортом. Продолжение следует!
С уважением, Ваш Вячеслав «Marpa» Шаров
По вопросам сюда => Marpa3d