网站开发技术期末考试题,做网站美工赚钱吗,电商网站功能模块图,天乐测绘网做网站吗二分查找 leetcode704
前面部分第4题#xff0c;包括使用条件等感谢代码随想录#xff1a;#xff09; leetcode704 二分查找用于在有序且不重复的元素列表中寻找需要的元素#xff0c;返回其位置或错误 当要求算法的时间复杂度在O#xff08;logn) 等带log的复杂度时包括使用条件等感谢代码随想录 leetcode704 二分查找用于在有序且不重复的元素列表中寻找需要的元素返回其位置或错误 当要求算法的时间复杂度在Ologn) 等带log的复杂度时可以考虑二分查找法 二分查找法中对于 区间 的定义 二分查找涉及的很多的边界条件逻辑比较简单但就是写不好。例如到底是 while(left right) 还是 while(left right)到底是right middle呢还是要right middle - 1呢 对于二分法的区间定义可以有闭区间、左闭右开、左开右闭等多种写法他们的含义是我们寻找的target与左右指针的关系 与此相关的自然就会产生循环条件的判断 以及 每次循环的左右指针的偏移 的定义问题 以下为闭区间版本的写法
// 学习版本二分查找
func search(nums []int, target int) int {high : len(nums) - 1low : 0for low high { //在闭区间中如[11]是有意义的mid : low (high-low)/2 //这样定义防止数字太大溢出if nums[mid] target {return mid} else if nums[mid] target { //缩小target所在的区间由于为闭区间可以舍弃上次的边界值high mid - 1} else {low mid 1}}return -1
}
左闭右开区间版本
// 左闭右开区间版本
func search(nums []int, target int) int {high : len(nums) //由于右开取不到最右边的数所以这里不用-1也不会超限low : 0for low high { //类似于[1,1)这样的区间是没有意义的mid : low (high-low)/2 //同样防止溢出if nums[mid] target {return mid} else if nums[mid] target {high mid //右开不需要舍弃右边值} else {low mid 1 //左开当前值不符合抛弃当前值}}return -1
}
704 学习 完整代码如下
package mainimport (fmt
)func main() {nums : []int{-1, 0, 3, 5, 9, 12}n : search(nums, 8)fmt.Println(n)
}//赖子玩法使用hashmap进行解决
/*func search(nums []int, target int) int {Abook : map[int]int{}for i, num : range nums {Abook[num] i}number, ok : Abook[target]if ok {return number}return -1
}
*/// 使用二分查找进行查询 个人版本对区间的定义理解不够
// 因此需要额外定义多种情况
/*func search(nums []int, target int) int {left, right : 0, len(nums)-1//如果该目标值直接大于或者小于nums中所有数直接返回-1if target nums[right] || target nums[left] {return -1}//为了避免与后面查询不到的情况避开我们这里直接设定两个值时的情况if nums[0] target {return 0}if nums[right] target {return right}for {mid : (left right) / 2 //偶数为中间往前一个数 奇数即为中间数//如果寻找到目标值。返回if nums[mid] target {return mid}//如果没有查询到目标值if math.Abs(float64(left-right)) 1 {return -1}if nums[mid] target { //目标大于中间值往后查找left mid} else { //nums[mid] target//目标小于中间值往前查询right mid}}}*/// 学习版本二分查找 闭区间
/*func search(nums []int, target int) int {high : len(nums) - 1low : 0for low high { //在闭区间中如[11]是有意义的mid : low (high-low)/2 //这样定义防止数字太大溢出if nums[mid] target {return mid} else if nums[mid] target { //缩小target所在的区间由于为闭区间可以舍弃上次的边界值high mid - 1} else {low mid 1}}return -1
}*/// 左闭右开区间版本
func search(nums []int, target int) int {high : len(nums) //由于右开取不到最右边的数所以这里不用-1也不会超限low : 0for low high { //类似于[1,1)这样的区间是没有意义的mid : low (high-low)/2 //同样防止溢出if nums[mid] target {return mid} else if nums[mid] target {high mid //右开不需要舍弃右边值} else {low mid 1 //左开当前值不符合抛弃当前值}}return -1
}
