二分查找

方法一：手动实现二分

golang实现C++中upper_bound & lower_bound_go lowerbound

package main  
  
import "fmt"  
  
func LowerBound(st, ed int, key int, arr []int) int {  
   left, right := st, ed-1  
   for left < right {  
      mid := (left + right) >> 1  
      if arr[mid] >= key {  
         right = mid  
      } else {  
         left = mid + 1  
      }  
   }  
   return right  
}  
  
func UpperBound(st, ed int, key int, arr []int) int {  
   left, right := st, ed-1  
   for left < right {  
      mid := (left + right) >> 1  
      if arr[mid] > key {  
         right = mid  
      } else {  
         left = mid + 1  
      }  
   }  
   return right  
}  
  
func main() {  
   arr := []int{1, 2, 2, 2, 2, 2, 2, 2, 3, 4}  
   low := LowerBound(0, len(arr), 2, arr)  
   up := UpperBound(0, len(arr), 2, arr)  
   fmt.Println(low)  
   fmt.Println(up)  
}

方法二：使用 sort 包

二分查找

对一个完整的有序数组进行二分查找

package main
 
import (
	"fmt"
	"sort"
)
 
func main() {
	// 定义一个有序切片
	nums := []int{1, 2, 3, 3, 3, 4, 5, 6, 7}
	// 查找第一个大于 3 的元素的下标
	index := sort.Search(len(nums), func(i int) bool { return nums[i] > 3 })
	fmt.Println("upper_bound index:", index)
	// 查找第一个大于等于 3 的元素的下标
	index = sort.Search(len(nums), func(i int) bool { return nums[i] >= 3 })
	fmt.Println("lower_bound index:", index)
}
 

对子切片中的元素进行二分查找，可通过改造 Search()函数的参数实现

package main
 
import (
	"fmt"
	"sort"
)
 
//LowerBound
/*
 * @input int st    起始位置
 * @input int ed    结束位置的后一位
 * @input int key   查找元素
 * @input []int arr 查找的数组
 * @return int      要查找的元素在子切片中的相对位置，在原切片中的位置为st+index
 */
func LowerBound(st, ed int, key int, arr []int) (index int) {
	return sort.Search(ed-st, func(i int) bool {
		return arr[st+i] >= key
	})
}
func UpperBound(st, ed int, key int, arr []int) (index int) {
	return sort.Search(ed-st, func(i int) bool {
		return arr[st+i] > key
	})
}
func main() {
	// 定义一个已排序的切片
	nums := []int{1, 2, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 10}
	//index为在子切片中的位置，对应原切片st+index
	index := LowerBound(2, 8, 5, nums)
	fmt.Println("lower_bound index:", index)
	index = UpperBound(2, 8, 5, nums)
	fmt.Println("upper_bound index:", index)
 
}

指向原始笔记的链接