折半查找算法的变形情况; 前后端各自有序,整体无序

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

``` package main import ( "fmt" ) // 一分为2, 肯定有一半是有序的 func BinarySearchDef(data []int, key int, low int, high int) int { if len(data) == 0 { return -1 } // 注意临界值 for low <= high { mid := low + (high-low)/2 fmt.Println(mid) fmt.Println(data[mid]) if key == data[mid] { return mid } // 如果 key 比中间值小 if key < data[mid] { if key == data[low] { return low } //如果key 比中间值小,但是比 low 位置上的值大 if key > data[low] { // 如果 key比中间值小, 比low位置上的值大, 同时 low 到 mid 之间的元素是无序的 if mid-1 >= low && data[low] >= data[mid-1] { return BinarySearchDef(data, key, low, mid-1) } // 有序则反查另一半 high = mid - 1 } if key < data[low] { if mid-1 >= low && data[low] >= data[mid-1] { return BinarySearchDef(data, key, low, mid-1) } low = mid + 1 } } if key > data[mid] { if key == data[high] { return high } if key > data[high] { if mid+1 <= high && data[mid+1] >= data[high] { return BinarySearchDef(data, key, mid+1, high) } // 有序则反查另一半, 因为该部分中肯定无对应的值 high = mid - 1 } if key < data[high] { if mid+1 <= high && data[mid+1] >= data[high] { return BinarySearchDef(data, key, mid+1, high) } low = mid + 1 } } } return -1 } func main() { data := []int{100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 121, 122, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} i := BinarySearchDef(data, 3, 0, len(data)-1) fmt.Println(i) } ```

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

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

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