二分查找

#golang #二分查找

方法一：手动实现二分

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 包

排序

参考：Golang sort包排序（详细全集）

方法一 ：sort.Slice()方法

package main  
  
import (  
   "fmt"  
   "sort"
)    
func main() {  
   arr := []int{8, 3, 5, 7, 1, 4}  
   sort.Slice(arr, func(i, j int) bool {  
      return arr[i] < arr[j]  
   })  
   fmt.Println(arr)  
}

方法二：在一开始时创建具有排序方法的切片

package main

import (
	"fmt"
	"sort"
)

func main() {
	arr := sort.IntSlice{8, 3, 5, 7, 1, 4}
	arr.Sort()
	fmt.Println(arr)
}

方法三 ：对自定义结构体的排序

package main

import (
	"fmt"
	"sort"
)

type Point struct {
	x, y int
}
type Points []Point

func (p Points) Len() int {
	return len(p)
}
func (p Points) Less(i, j int) bool {
	if p[i].x != p[j].x {
		return p[i].x < p[j].x
	}
	return p[i].y < p[j].y
}
func (p Points) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func main() {
	arr := Points{{1, 2}, {1, 3}, {2, 3}}
	sort.Sort(arr)
	fmt.Println(arr)
}

注意：默认的 sort() 会自动选择快排、堆排序和插入排序，是不稳定排序，如果需要稳定排序，请使用 sort.Stable()(其使用的是归并排序)