美文网首页
二分查找

二分查找

作者: 甜点cc | 来源:发表于2022-08-08 10:05 被阅读0次

    二分查找又称折半查找,整体思路就是一步一步缩小查找范围,直到找到目标值,运用递归实现。

    思路分析

    二分查找的思路:比如我们要查找的数是findVal

    使用的是Golang

    1. arr 是一个有序数组,并且是从小到大排序

    2. 先找到中间的下标 middle = (leftindex + rightindex) / 2, 然后让中间下标的值和findVal进行比较

    • 2.l. 如果 arr[middle] > findVal, 就应该向 leftindex---(middle-1)

    • 2.2. 如果 arr[middle] < findVal, 就应该向 middle+1---rightindex

    • 2.3. 如果 arr[middle] = findVal, 就找到了

    • 2.4. 上面的2.1,2.2,2.3的逻辑递归执行

    1. 想一下,怎么样的情况下,就说明找到递归退出的条件
      if leftindex > rightindex{
          // 找不到
          return
      }
    

    有了上面的分析思路,接下来看一下代码实现。

    代码实现

    package main
    
    import "fmt"
    
    // 二分查找函数
    // 递归, 边界条件
    func binaryFind(arr *[6]int, leftIndex int, rightIndex int, findVal int) {
        // 找不到的情况
        // 退出递归的条件
        if leftIndex > rightIndex {
            fmt.Println("找不到")
            return
        }
    
        // 递归条件
        // 先找到中间下标,折半
        mid := (leftIndex + rightIndex) / 2
        if (*arr)[mid] > findVal {
            // findVal 在左边 leftIndex - (mid - 1)
            binaryFind(arr, leftIndex, mid-1, findVal)
        } else if (*arr)[mid] < findVal {
            // findVal 在右边 (mid + 1) - rightIndex
            binaryFind(arr, mid+1, rightIndex, findVal)
        } else {
            // 找到了
            fmt.Printf("找到了,下标为%v", mid)
        }
    }
    
    func main() {
        // 有序数组
        var arr [6]int = [6]int{1, 8, 10, 89, 1000, 1234}
        fmt.Println("arr = ", arr)
        // 二分查找/折半查找
        binaryFind(&arr, 0, len(arr), 8)
    }
    
    
    arr =  [1 8 10 89 1000 1234]
    找到了,下标为1
    

    🎈🎈🎈

    🌹 持续更文,关注我,你会发现一个踏实努力的宝藏前端😊,让我们一起学习,共同成长吧。

    🎉 喜欢的小伙伴记得点赞关注收藏哟,回看不迷路 😉

    🎁 欢迎大家评论交流, 蟹蟹😊

    相关文章

      网友评论

          本文标题:二分查找

          本文链接:https://www.haomeiwen.com/subject/fbkwwrtx.html