前提

  • 列表有序

复杂度

O(log n)

code

package main

import "fmt"

func main() {
	arr := []int{1,2,3,4,5,6}
	index := binarySearch(arr, 3)
	fmt.Println(index)
}

func binarySearch(list []int, item int) int {
	o := 0
	low := 0
	high := len(list) - 1

	for low <= high {
		o++
		mid := (low + high) / 2
		guess := list[mid]
		fmt.Printf("item: %d ---", item)
		fmt.Printf("low: %d ---", low)
		fmt.Printf("high: %d ---", high)
		fmt.Printf("mid: %d ---", mid)
		fmt.Printf("guess: %d ---", guess)
		fmt.Println("o: ", o)

		if guess == item {
			return mid
		}
		if guess > item {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

output

item: 3 ---low: 0 ---high: 5 ---mid: 2 ---guess: 3 ---o:  1
index:  2