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
}
你好。输入是一个排序数组,数组的中心,期望的值。你真的需要找到你正在寻找的东西。原则上,我处理了搜索,但是在第一次出现所需的之后,它就结束了,我无法以任何方式用找到的所需数字的位置来固定结果数组的填充。这个怎么做?
升级版:
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
}
使用二进制搜索的变体来查找与给定元素匹配的最左边和最右边的元素,从而获得一系列索引。这里是 Wikipedia,转移到 golang 并不难。
伪代码:
当你发现
sorted[mid] == target- 你只需要收集右边和左边的邻居,只要它们匹配所需的值......你不能不绕过你的原始切片(不然怎么办)只是去左右一排 - 你需要走路示例(grabNeigh 函数实现的邻居集合)
https://go.dev/play/p/5RLV3Y5mNlA