二分查找是分治法的一个典型应用,通过二分查找,可以在O(logN)时间复杂度中从一个有序的数组中找出指定的元素。这也是面试中经常遇到的题目,今天就来看一下二分查找的一些变形题。

leetcode 704:二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func search(arr []int, v int) int {
if len(arr) == 0 {
return -1
}

p := 0
q := len(arr) - 1
for p <= q {
mid := (p + q) >>1
if arr[mid] == v {
return mid
}

if arr[mid] < v {
p = mid + 1
} else {
q = mid - 1
}

}
return -1
}

leetcode 1095: 山脉数组中查找目标值

山脉数组就是先递增,后递减的一个数组,比如:[1,2,3,4,5,3,1]

要在山脉数组中查找指定数字,我们可以先通过二分查找,找出最大的那个数,将数组分成两部分,然后分别对这两部分进行二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

func findNum(arr []int, num int) bool {
if len(arr) == 0 {
return false
} else if len(arr) == 1 {
return arr[0] == num
}
// 首先,找出数组中最大值的下标
maxIdx := findMax(arr, 0)
// 将数组分割成两部分,分别执行二分查找
return binSearch(arr[:maxIdx], num, true) || binSearch(arr[maxIdx:], num, false)
}

// 二分查找,查找山脉数组的最大值
func findMax(arr []int, i int) int {
if len(arr) == 1 {
return i
}

mid := (len(arr) - 1) / 2

if mid+1 < len(arr) && arr[mid+1] > arr[mid] {
return findMax(arr[mid+1:], i+mid+1)
} else {
return findMax(arr[:mid+1], i)
}
}

func binSearch(arr []int, num int, asc bool) bool {
if len(arr) == 0 {
return false
}
l, r := 0, len(arr)-1
for l < r {
mid := (l + r) >> 1
if arr[mid] == num {
return true
}

if arr[mid] > num {
if asc {
r = mid - 1
} else {
l = mid + 1
}
} else {
if asc {
l = mid + 1
} else {
r = mid - 1
}
}
}
return arr[l] == num
}

旋转数组的最小值

这是剑指offer里面的一道原题。把一个升序数列在某个位置进行旋转,导致前面若干个元素被移动到数组末尾,输出数组的最小值。

比如数组[1,2,3,4,5,6]index=3的地方发生rotate,变成[4,5,6,1,2,3],在旋转后的数组中找出最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func MinOfRotateArr(arr []int) int {
if len(arr) == 0 {
panic("invalid array")
}
l, r := 0, len(arr)-1
// 只有一个元素或者旋转后还是自身
if l == r || arr[l] < arr[r] {
return arr[l]
}

for l+1 < r {
mid := (l + r) / 2
if arr[l] <= arr[mid] {
l = mid
} else {
r = mid
}
}
return arr[r]
}

面试题 排序矩阵查找

这是剑指offer里面的一道原题。给定M×N矩阵,每一行、每一列都按升序排列,请编写代码找出某元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix)==0||len(matrix[0])==0{
return false
}
rows:=len(matrix)
cols :=len(matrix[0])

r := 0
c := cols - 1
for r < rows && c >= 0 {
if n := matrix[r][c]; n == target {
return true
} else if n > target {
c--
} else {
r++
}
}
return false
}

总结

二分查找,主要是利用数组的性质,应用分治法进行求解。