1.本节知识点二分查找知识点二分查找代码实现二分查找变种实现完整代码2.二分查找知识点查找的数据必须是一个有序的集合查找思想类似于分治思想,每次通过区间中间的数对比,将待查的区间缩小为之前的一半,直到找到要查询的元素时间复杂度 O(logn)二分查找代码实现查找有序数组中给定的值(最简单的一种)

func BinarySearch(arr []int,value int) int{    low ,height :=0,len(arr)-1 //最小索引,最大索引    for low<=height{        min :=low+(height-low)/2        if arr[mid]==value{            return mid        }else if arr[mid]<value{            low=mid+1        }else{            height=mid-1        }    }    return -1 //如里没有找到返回 -1}func TestBinarySearch(t *testing.T) {	arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}	i := BinarySearch(arr, 5) //从数组中找到值等于5的下标	t.Log(i)} 

查找第一个值等于给定值的元素 (数组从小到大排列)

//查找第一个值等于给定值的元素 (数组从小到大排列) []int{1, 3, 4, 5, 6, 8, 8, 8, 11, 18} 查找8 返回索引5func firstOccurrenceBinarySearch(arr []int ,value int)int{    low,height :=0,len(arr)-1 //定义最小值与最大值    for low<=height{ //注意这里的<=条件        mid :=low +(height-low)/2 //防止数值太大导致的溢出问题        if arr[mid]==value{            //如果找到了值,判断是不是第一个符合条件的值            if mid==0||arr[mid-1] !=value{                // 如果是第一个元素或者前一个元素不是等于查找的值,可以判定是第一个值                return mid            }else{                //如果不是则继续向左寻找                height=mid-1            }        }else if arr[mid]<value{            low=mid+1        }else{            height =mid-1        }            }    return -1}

查找最后一个值等于给定值的元素(数组从小到大排列)

//查找最后一个值等于给定值的元素 (数组从小到大排列) []int{1, 3, 4, 5, 6, 8, 8, 8, 11, 18} 查找8 返回索引7func LastOccurrenceBinarySearch(arr []int,value int) int{    low ,height :=0,len(arr)-1    for low<=height{        mid :=low +(height-low)/2        if arr[mid]<value{            low=mid+1        }else if arr[mid]>value{            height=mid-1        }else{            //如果是最后一个元素或者下一个元素不等说查找的值,则是要找的那个值            if mid ==len(arr)-1||mid[mid+1] !=value{                return mid            }        }    }}

查找第一个大于等于给定值的元素(数组从小到大排列)

//查找第一个大于等于给定值的元素(数组从小到大排列) []int{1, 3, 6, 8, 11, 18} 查找4 返回索引2func  firstGreaterOrEqual(arr []int,value int){    low,height :=0,len(arr)-1    res :=-1    for low<=height{        mid :=low +(height-low)/2        if arr[mid]>=value{            res=mid            //计算向左查看            height=mid-1        }else{            low=mid+1        }    }    return res}

查找最后一个小于等说给定值的元素(数组从小到大排列)

//比如，数组中存储了这样一组数据：3，5，6，8，9，10。最后一个小于等于 7 的元素就是6func lastLessOrEqual(arr []int, value int) int {    low,height :=0,len(arr)-1    res:=-1    for low<=height{        mid :=low +(height-low)/2        if arr[mid]<=value{           res=mid            low=mid+1 //继续向右查,看是不是还有符合条件的        }else{            height=mid-1        }    }    return res}

补充:完整代码

 /* * @author biubiu @date:2023/9/1 */ package binarySearchDemo  import (     "testing" )  // 简单二分查找法实现 func BinarySearch(arr []int, value int) int {     low, height := 0, len(arr)-1     for low <= height {         mid := low + (height-low)/2         if arr[mid] == value {             return mid         } else if arr[mid] < value {             low = mid + 1         } else {             height = mid - 1         }     }     return -1 }  func TestBinarySearch(t *testing.T) {     arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}     i := BinarySearch(arr, 5)     t.Log(i) }  // 查找第一个值等于给定值的元素 (数组从小到大排列) []int{1, 3, 4, 5, 6, 8, 8, 8, 11, 18} 查找8 返回索引5 func firstOccurrenceBinarySearch(arr []int, value int) int {     low, height := 0, len(arr)-1      for low <= height {         mid := low + (height-low)/2         if arr[mid] == value {              //找到目标元素,检查是不是第一个等于value的元素             if mid == 0 || arr[mid-1] != value {                  return mid             } else {                 //继续向左半部分查找                 height = mid - 1             }          } else if arr[mid] < value {             low = mid + 1          } else {              height = mid - 1         }     }     return -1 } func TestFirstOccurrenceBinarySearch(t *testing.T) {     arr := []int{1, 3, 4, 5, 6, 8, 8, 8, 11, 18}     i := firstOccurrenceBinarySearch(arr, 8)     t.Log(i) }  // 查找最后一个值等于给定值的元素 (数组从小到大排列) []int{1, 3, 4, 5, 6, 8, 8, 8, 11, 18} 查找8 返回索引7 func lastOccurrenceBinarySearch(arr []int, value int) interface{} {     low, height := 0, len(arr)-1     for low <= height {         mid := low + (height-low)/2         if arr[mid] < value {             low = mid + 1         } else if arr[mid] > value {             height = mid - 1         } else {             if mid == len(arr)-1 || arr[mid+1] != value {                 return mid             }         }     }     return -1 } func TestLastOccurrenceBinarySearch(t *testing.T) {     arr := []int{1, 3, 4, 5, 6, 8, 8, 8, 11, 18}     i := lastOccurrenceBinarySearch(arr, 8)     t.Log(i) }  // 查找第一个大于等于给定值的元素(数组从小到大排列) []int{1, 3, 6, 8, 11, 18} 查找4 返回索引6 func TestFirstGtOccurrenceBinarySearch(t *testing.T) {     arr := []int{3, 4, 6, 7, 10}     i := FirstGtOccurrenceBinarySearch(arr, 5)     t.Log(i) }  func FirstGtOccurrenceBinarySearch(arr []int, value int) interface{} {     low, height := 0, len(arr)-1     res := -1     for low <= height {         mid := low + (height-low)/2         if arr[mid] >= value {             res = mid             height = mid - 1         } else {             low = mid + 1         }     }     return res } func lastLessOrEqual(arr []int, value int) int {     low, height := 0, len(arr)-1     res := -1     for low <= height {         mid := low + (height-low)/2         if arr[mid] <= value {             res = mid             low = mid + 1         } else {             height = mid - 1         }     }     return res }  // 查找最后一个小于等于给定值的元素。比如，数组中存储了这样一组数据：3，5，6，8，9，10。最后一个小于等于 7 的元素就是6 func TestLastLessOrEqual(t *testing.T) {     arr := []int{3, 4, 6, 7, 10}     i := lastLessOrEqual(arr, 5)     t.Log(i) }