RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 1410095
Accepted
Quester
Quester
Asked:2022-07-15 20:34:33 +0000 UTC2022-07-15 20:34:33 +0000 UTC 2022-07-15 20:34:33 +0000 UTC

二分查找只返回第一个值

  • 772
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
}
golang
  • 2 2 个回答
  • 214 Views

2 个回答

  • Voted
  1. MBo
    2022-07-16T00:45:15Z2022-07-16T00:45:15Z

    使用二进制搜索的变体来查找与给定元素匹配的最左边和最右边的元素,从而获得一系列索引。这里是 Wikipedia,转移到 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
    
    • 2
  2. Best Answer
    Maksim Fedorov
    2022-07-16T00:10:49Z2022-07-16T00:10:49Z

    当你发现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
    }
    
    • 1

相关问题

  • windows上的protoc编译错误

  • 递归打印包依赖

  • Golang 算法 XTEA ECB 库“golang.org/x/crypto/xtea”

  • 如何将 IMEI 转换为字节并返回 golang

  • 如何创建文件并将其移动到新目录?

  • go中的函数参数中是否有cv-qualifier的类似物?

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    我看不懂措辞

    • 1 个回答
  • Marko Smith

    请求的模块“del”不提供名为“default”的导出

    • 3 个回答
  • Marko Smith

    "!+tab" 在 HTML 的 vs 代码中不起作用

    • 5 个回答
  • Marko Smith

    我正在尝试解决“猜词”的问题。Python

    • 2 个回答
  • Marko Smith

    可以使用哪些命令将当前指针移动到指定的提交而不更改工作目录中的文件?

    • 1 个回答
  • Marko Smith

    Python解析野莓

    • 1 个回答
  • Marko Smith

    问题:“警告:检查最新版本的 pip 时出错。”

    • 2 个回答
  • Marko Smith

    帮助编写一个用值填充变量的循环。解决这个问题

    • 2 个回答
  • Marko Smith

    尽管依赖数组为空,但在渲染上调用了 2 次 useEffect

    • 2 个回答
  • Marko Smith

    数据不通过 Telegram.WebApp.sendData 发送

    • 1 个回答
  • Martin Hope
    Alexandr_TT 2020年新年大赛! 2020-12-20 18:20:21 +0000 UTC
  • Martin Hope
    Alexandr_TT 圣诞树动画 2020-12-23 00:38:08 +0000 UTC
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5