Бинарный поиск двет только первое значние

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 шт):

Автор решения: Maksim Fedorov

Когда вы нашли, что 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
}
→ Ссылка
Автор решения: MBo

Примените разновидности бинарного поиска для нахождения самого левого и самого правого элемента, совпадающего с заданным, таким образом получите диапазон индексов. Вот в википедии есть, на 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
→ Ссылка