二分查找是分治法的一个典型应用，通过二分查找，可以在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
}

总结

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