二分查找
二分搜索是一个效率很高的算法. 一个良好实现的二分搜索算法, 其时间复杂度可以达到Θ(log??), 而空间复杂度只有??(1).
要注意二分搜索的适用场景:
依赖顺序表结构
数据本身必须有序
数据量相对比较元素的开销要足够大 -- 不然遍历即可
数据量相对内存空间不能太大 -- 不然顺序表装不下
实现
- func binarySearch(a []int, t int) int{
- l,r := 0,len(a)-1
- for l<=r {
- mid := l + (r-l)>>1
- if a[mid] == t {
- return mid
- } else if a[mid] <t {
- l = mid+1
- } else {
- r = mid-1
- }
- }
- return -1
- }
二分法技术 sqrt
- func sqrt(x float64, p float64) float64 {
- l, r := 0.0, x
- for {
- mid := l + (r-l)/2.0
- t := mid * mid
- if math.Abs(x-t) < p {
- return mid
- } else if t> x {
- r = mid
- } else {
- l = mid
- }
- }
- }
变体
第一个等于目标值的元素下标
- func binarySearchFirst(a []int, t int) int{
- l,r := 0,len(a)-1
- for l<r {
- mid := l + (r-l)>>1
- if a[mid] <t {
- l = mid+1
- } else {
- r = mid
- }
- }
- if a[l] == t {
- return l
- }
- return -1
- }
最后一个等于目标值的元素下标
- func binarySearchLast(a []int, t int) int{
- l,r := 0,len(a)-1
- for l<r {
- mid := l + (r-l)>>1
- if a[mid] <= t {
- l = mid
- } else {
- r = mid - 1
- }
- }
- if a[l] == t {
- return l
- }
- return -1
- }
第一个不小于目标值的元素下标
- func binarySearch(a []int, t int) int{
- l,r := 0,len(a)-1
- for l<=r {
- mid := l + (r-l)>>1
- if a[mid] <t {
- l = mid + 1
- } else {
- r = mid - 1
- }
- }
- if l < len(a) {
- return l
- }
- return -1
- }
第一个大于目标值的元素下标
- func binarySearch(a []int, t int) int{
- l,r := 0,len(a)-1
- for l<=r {
- mid := l + (r-l)>>1
- if a[mid] <= t {
- l = mid + 1
- } else {
- r = mid - 1
- }
- }
- if l <len(a) {
- return l
- }
- return -1
- }
小于目标值的元素的最大下标
先找到不小于目标值的最小下标
向前查看一步即是结果
有序数组中目标值的个数
找到目标值最小下标
找到目标值最大下标
计算个数
- func splitSearch(arr []int, t int, i int, j int) int {
- for i <= j {
- // 获取中间值
- mid := i + (j-i)>>1
- // 刚好相等, 得到答案
- if arr[mid] == t {
- return mid
- } else if arr[mid] <t {
- //mid-j 之间有序, 则使用正常二分查找
- if t <= arr[j] {
- i = mid + 1
- } else {
- j = mid - 1
- }
- } else {
- //i-mid 之间有序, 使用正常二分查找
- if t>= arr[i] {
- j = mid - 1
- } else {
- i = mid + 1
- }
- }
- }
- return -1
- }
- func lengthOfLIS(nums []int) int {
- ret := make([]int,0,len(nums))
- for i:=0;i<len(nums);i++{
- t := find(ret,nums[i])
- if t == -1 {
- ret = append(ret,nums[i])
- } else {
- ret[t] = nums[i]
- }
- }
- return len(ret)
- }
- // 找到第一个大于或等于 k 的位置
- func find(nums []int, k int) int {
- ll := len(nums) -1
- if ll <0 {
- return -1
- }
- l, r := 0, ll
- for l < r {
- mid := l + (r-l)>>1
- if nums[mid] == k {
- return mid
- } else if nums[mid]> k {
- r = mid
- } else {
- l = mid + 1
- }
- }
- if l == ll && nums[l] < k {
- return -1
- }
- return l
- }
来源: http://www.bubuko.com/infodetail-3459345.html