概念
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
查找速度
时间复杂度也是 O(logn)
二分查找的递归与非递归实现
非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func Bsearch(arr []int, n, value int) int {
low := 0
high := len(arr)
for low <= high {
mid := low + (high-low)>>1
if arr[mid] == value {
return mid
} else if arr[mid] < value {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}
|
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
| func BsearchRecursion(arr []int, low, high, value int) int {
if low > high {
return -1
}
mid := low + ((high - low) >> 1)
if arr[mid] == value {
return mid
} else if arr[mid] < value {
return BsearchRecursion(arr, mid+1, high, value)
} else {
return BsearchRecursion(arr, low, mid-1, value)
}
}
|
应用场景的局限性
- 二分查找只能用在数据是通过顺序表来存储的数据结构上。如果你的数据是通过其他数据结构存储的，则无法应用二分查找
- 二分查找对这一点的要求比较苛刻，数据必须是有序的。
- 如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。
- 分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。
二分查找变体
变体一：查找第一个值等于给定值的元素
有序数据集合中存在重复的数据，我们希望找到第一个值等于给定值的数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func Bsearch2(arr []int, n, value int) int {
low := 0
high := len(arr)
for low <= high {
mid := low + (high-low)>>1
if arr[mid] > value {
high = mid - 1
} else if arr[mid] < value {
low = mid + 1
} else {
if (mid == 0) || (arr[mid-1] != value) {
return mid
} else {
high = mid - 1
}
}
}
return -1
}
|
变体二：查找最后一个值等于给定值的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func Bsearch3(arr []int, n, value int) int {
low := 0
high := len(arr)
for low <= high {
mid := low + (high-low)>>1
if arr[mid] > value {
high = mid - 1
} else if arr[mid] < value {
low = mid + 1
} else {
if (mid == n-1) || (arr[mid+1] != value) {
return mid
} else {
low = mid + 1
}
}
}
return -1
}
|
变体三：查找第一个大于等于给定值的元素
a[mid]小于要查找的值 value，那要查找的值肯定在[mid+1, high]之间，所以，我们更新 low=mid+1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func Bsearch4(arr []int, n, value int) int {
low := 0
high := len(arr)
for low <= high {
mid := low + (high-low)>>1
if arr[mid] >= value {
if (mid == 0) || (arr[mid-1] < value) {
return mid
} else {
high = mid - 1
}
} else if arr[mid] < value {
low = mid + 1
}
}
return -1
}
|
变体四：查找最后一个小于等于给定值的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func Bsearch5(arr []int, n, value int) int {
low := 0
high := len(arr)
for low <= high {
mid := low + (high-low)>>1
if arr[mid] > value {
high = mid - 1
} else if arr[mid] <= value {
if (mid == n-1) || (arr[mid+1] > value) {
return mid
} else {
low = mid + 1
}
}
}
return -1
}
|