Бинарный поиск двет только первое значние
package main
import (
"log"
)
func BinarySearch(sorted, result []int, target int) int {
lendata := len(sorted) - 1
var mid int
first := 0
for first < lendata {
mid = (first + lendata) / 2
if target > sorted[mid] {
first += 1
}
if target < sorted[mid] {
lendata -= 1
}
if target == sorted[mid] {
//здесь нужно добавить искомый в массив и ПРОДОЛЖИТЬ выполнение функции пока текущий элемент не станет больше или меньше искомого
return mid
}
}
if sorted[first] != target && sorted[lendata] != target {
return 0
}
return mid
}
Привет. На вход дается отсортированный массив, центр массива, искомое значение. Нужно собственно найти искомое. Я впринципе справился с поиском, но он, после первого вхождения искомого, завершается и никак не могу прикрутить сюда заполнение массива result найденными позициями искомого числа. Как бы такое сделать?
UPD:
package main
import (
"log"
)
/* Находит первое вхождение искомого */
func BinarySearch(sorted, result []int, target int) []int {
// изначально границы поиска между нулевым и последний элементом
lendata := len(sorted)
first := 0
//чтобы сохранять сюда середину текущей области поиска и иметь к ней доступ вне цикла
var mid int
//Идем от начальной границы до конечной
for first < lendata {
//При первом вхождении искомого выходим из цикла
if target == sorted[mid] {
break
}
//если искомое больше чем значение в середине области поиска,
//началом области поиска становится то значение, которое было серединой области +1
//так как значение по середине тоже не искомое
if target > sorted[mid] {
log.Println(">", mid)
first = mid + 1
}
//если искомое меньше, чем значение посередине области поиска,
//то конечной границей области поиска становится середина-1
//так как значение посередине не подошло тоже
if target < sorted[mid] {
log.Println("<", mid)
lendata = mid - 1
}
//находим заново середину так как в условиях передвинули границы
mid = (first + lendata) / 2
}
//добавляем в массив вхождений первый индекс содержащий искомое
result = append(result, mid)
//вызов нахождения повторных вхождений искомого в массиве по первому индексу который содержит искомое
result = FindRepeated(target, mid, sorted, result)
return result
}
//Здесь ничего интересного. QuickSort тот, что я сделал в одном из заданий уровня, чтобы не писать заново
//использую его
//Сортировка нужна так как бинарный поиск работает только на отсортированном массиве(слайсе)
func make_for_Binary(target int) {
slc, result := make([]int, 0), make([]int, 0)
slc = append(slc, 32, 1, 1, 1, 2, 5, 12, 87, 87, 87, 87, 87, 87, 87, 45, 344, 344, 12, 3, 89, 90, 43)
slc = QuickSort(slc)
//здесь вывод чтобы можно было убедится что поиск выводит индексы корректно и ничего не сдвигается
log.Println(slc)
result = BinarySearch(slc, result, target)
//дополнительно сортирую все индексы с искомым для удобства восприятия
result = QuickSort(result)
log.Println(result)
}
//Принимает первое индекс с искомым и опираясь на него находит остальные вхождения искомого.
func FindRepeated(target, position int, sorted, result []int) []int {
//Буфер
p := position
//проверка всех индексов следующих за первым вхождением
for position <= len(sorted)-1 {
//не допускаем выход за пределы массива(слайса), так как иначе будет паника, так как индекс не может быть > длины массива
if position+1 >= len(sorted) {
break
}
//все повторные вхождения после первого индекса вносятся в результирующий слайс
if sorted[position+1] == target {
//и передвигаемся на следующий в порядке убывания элемент
position += 1
result = append(result, position)
} else {
break
}
}
position = p
for position >= 0 {
if position-1 <= 0 {
break
}
if sorted[position-1] == target {
position -= 1
result = append(result, position)
} else {
break
}
}
return result
}
Ответы (2 шт):
Когда вы нашли, что sorted[mid] == target — вам остается собрать соседей справа и слева, пока они совпадают с искомым значением... без обхода вашего исходного слайса не обойтись (как иначе) просто идете подряд вправо и влево — надо пройтись
Пример (сбор соседей реализован функцией grabNeigh)
https://go.dev/play/p/5RLV3Y5mNlA
type Op int
const (
_ Op = iota
Right
Left
)
func BinarySearch(input []int, target int) []int {
var res []int
low := 0
hight := len(input) - 1
for low < hight {
m := low + (hight-low)/2
if m < 1 {
return res
}
if target > input[m] {
low += 1
} else if target < input[m] {
low -= 1
} else {
// Мы нашли наше значение, осталось пройтись влево и впарво собрать
res = append(res, m)
// Берем равных соседей справа, если есть
r := grabNeigh(input, m, target, Right)
res = append(res, r...)
// Берем равных соседей слева, если есть
l := grabNeigh(input, m, target, Left)
res = append(l, res...)
return res
}
}
return res
}
func grabNeigh(input []int, pos int, target int, op Op) []int {
var buf []int
hight := len(input) - 1
var compare func(l int, r int) bool
var loopPredic bool
var offset func(pos *int)
if op == Right {
loopPredic = pos < hight
offset = func(pos *int) { *pos += 1 }
compare = func(l int, r int) bool {
return l < r
}
}
if op == Left {
loopPredic = pos > 0
offset = func(pos *int) { *pos -= 1 }
compare = func(l int, r int) bool {
return l > r
}
}
for loopPredic {
offset(&pos)
if compare(target, input[pos]) {
return buf
}
buf = append(buf, pos)
}
return buf
}
Примените разновидности бинарного поиска для нахождения самого левого и самого правого элемента, совпадающего с заданным, таким образом получите диапазон индексов. Вот в википедии есть, на golang переложить нетрудно.
Псевдокод:
function binary_search_leftmost(A, n, T):
L := 0
R := n
while L < R:
m := floor((L + R) / 2)
if A[m] < T:
L := m + 1
else:
R := m
return L
function binary_search_rightmost(A, n, T):
L := 0
R := n
while L < R:
m := floor((L + R) / 2)
if A[m] > T:
R := m
else:
L := m + 1
return R - 1