思路分析

二分查找 - 图1

代码实现

  1. package main
  3. import "fmt"
  5. // 二分查找函数
  6. // 递归， 边界条件
  7. func binaryFind(arr *[6]int, leftIndex int, rightIndex int, findVal int) {
  8.     // 找不到的情况
  9.     // 退出递归的条件
  10.     if leftIndex > rightIndex {
  11.         fmt.Println("找不到")
  12.         return
  13.     }
  15.     // 递归条件
  16.     // 先找到中间下标，折半
  17.     mid := (leftIndex + rightIndex) / 2
  18.     if (*arr)[mid] > findVal {
  19.         // findVal 在左边 leftIndex - (mid - 1)
  20.         binaryFind(arr, leftIndex, mid-1, findVal)
  21.     } else if (*arr)[mid] < findVal {
  22.         // findVal 在右边 (mid + 1) - rightIndex
  23.         binaryFind(arr, mid+1, rightIndex, findVal)
  24.     } else {
  25.         // 找到了
  26.         fmt.Printf("找到了，下标为%v", mid)
  27.     }
  28. }
  30. func main() {
  31.     // 有序数组
  32.     var arr [6]int = [6]int{1, 8, 10, 89, 1000, 1234}
  33.     fmt.Println("arr = ", arr)
  34.     // 二分查找/折半查找
  35.     binaryFind(&arr, 0, len(arr), 8)
  36. }
  39. arr =  [1 8 10 89 1000 1234]
  40. 找到了，下标为1