甜点cc

V1

2022/08/08阅读:15主题:蔷薇紫

二分查找

思路分析

二分查找的思路:比如我们要查找的数是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{18108910001234}
 fmt.Println("arr = ", arr)
 // 二分查找/折半查找
 binaryFind(&arr, 0len(arr), 8)
}


arr =  [1 8 10 89 1000 1234]
找到了,下标为1

🎈🎈🎈

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

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

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

分类:

后端

标签:

后端

作者介绍

甜点cc
V1