go 二分查找

letterbeezps · · 488 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

# go 二分查找 ## 二分查找 给定一个有序数组 [1,2,4,6,8,8,10],再给定一个target值,此处以 8 为例,一般有4个查询目标 1. 从左向右第一个大于等于target的值的下标 2. 从左向右第一个大于target的值的下标 3. 从左向右最后一个小于等于target的值的下标 4. 从左向右最后一个小target的值的下标 3 和 4 是 1 和 2 的对立面,而1 和 2本质上是同一个目标 ## code ```go package main import "fmt" var arrs = []int{1,2,4,6,8,8,10} func main () { fmt.Printf("before arr: %v\n", arrs) up_equal := binary_search_up_equal(arrs, 8) fmt.Printf("the index of element which first ge %d is %d\n", 8, up_equal) up := binary_search_up(arrs, 8) fmt.Printf("the index of element which first g %d is %d\n", 8, up) down_equal := binary_search_down_equal(arrs, 8) fmt.Printf("the index of element which first le %d is %d\n", 8, down_equal) down := binary_search_down(arrs, 8) fmt.Printf("the index of element which first l %d is %d\n", 8, down) } // 第一个大于等于 8 func binary_search_up_equal(arrs []int, target int) int { l, r := 0, len(arrs) - 1 for l < r { mid := (l+r) / 2 if arrs[mid] < target { l = mid + 1 } else { r = mid } } return l } // 第一个大于 8 func binary_search_up(arrs []int, target int) int { l, r := 0, len(arrs) - 1 for l < r { mid := (l+r) / 2 if arrs[mid] <= target { l = mid + 1 } else { r = mid } } return l } // 最后一个小于等于 8 func binary_search_down_equal(arrs []int, target int) int { l, r := 0, len(arrs) - 1 for l < r { mid := (l+r+1) / 2 if arrs[mid] > target { r = mid - 1 } else { l = mid } } return l } // 最后一个小于 8 func binary_search_down(arrs []int, target int) int { l, r := 0, len(arrs) - 1 for l < r { mid := (l+r+1) / 2 if arrs[mid] >= target { r = mid - 1 } else { l = mid } } return l } ``` ## 返回值 * before arr: [1 2 4 6 8 8 10] * the index of element which first ge 8 is 4 * the index of element which first g 8 is 6 * the index of element which first le 8 is 5 * the index of element which first l 8 is 3

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

488 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传