go语言算法版--冒泡排序和二分查找-吃透二分查找
程序员文章站
2024-03-20 09:53:58
...
//二分查找 返回找到num的index 时间复杂度是logn
// 循环次数 1 2 3 。。。 x
// n数 n/2 n/4 n/8 ... n/(2^x)
//也就是当n个数为1,需要经历的查找次数与n的关系是 n/(2^x) = 1 -->x=logn
func binarySearch(ints []int, num int) int {
len := len(ints)
startIndex := 0
endIndex := len - 1
for startIndex <= endIndex {//循环条件
midIndex := startIndex + (endIndex-startIndex)/2
if ints[midIndex] == num {
return midIndex
}
if ints[midIndex] < num {
startIndex = midIndex + 1
} else {
endIndex = midIndex - 1
}
}
return -1
}
//冒泡排序 时间复杂度n^2
func bubbleSort(ints []int) {
len := len(ints)
flag := true
for i := 0; i < len-1; i++ {
for j := 0; j < len-1-i; j++ {
if ints[j] > ints[j+1] {
flag = false
ints[j], ints[j+1] = ints[j+1], ints[j]
}
}
if !flag {
flag = true
} else {
return
}
}
}
//快速排序
//插入排序
//归并排序
func main() {
ints := []int{1, 3, 6, 9, 2, 0, 4, 8, 2, 5, 0, 12, 45, 32, 78, 65}
bubbleSort(ints)
fmt.Println(ints)
ret := binarySearch(ints, 13)
fmt.Println(ret)
}
上一篇: 排序算法+二分查找
下一篇: 二分查找的时间复杂度
推荐阅读
-
go语言算法版--冒泡排序和二分查找-吃透二分查找
-
算法-排序(冒泡排序,选择排序,插入排序)和查找(二分查找)
-
排序算法和二分查找
-
JAVA冒泡排序和二分查找的实现
-
JAVA冒泡排序和二分查找的实现
-
Java基础知识回顾第一篇 - 数组和List之间的相互转换 | 二分法查找 | 冒泡排序 博客分类: Java基础知识回顾 冒泡排序二分法查找Java基础
-
PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解_PHP
-
PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解_PHP
-
js基本算法:冒泡排序,二分查找的简单实例
-
PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解