本文以Golang为例

二分通常的写法

1
2
3
4
5
6
7
8
9
10
11
12
func findNumInArray(x int, arr []int) (idx int) {
	l, r := 0, len(arr)
	for r-l > 0 {
		mid := int(uint(r+l) >> 1)
		if arr[mid] < x {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}

二分需要注意的地方其实就是for r-l > 0，l = mid + 1，r = mid，return l

也有人的写法是其他的如l = mid,return l+1等。 但是在很多库中（STLlower_bound,golangsort.Find）判断条件的写法都是我上面的这样

这里就讲下为什么这样。（仅个人看法）

左闭右开原则

编程里大家都遵循数组取左闭右开的，arr数组为[start,end)[start,end)，length就是end−startend-start，不为啥，就是方便，墨守成规

数组是这样表示，一些潜在的“范围”的概念也是如此表示,比如STL中sort(arr,arr+arr.length)

说回二分，二分中是在把一个范围一步步缩小到一个点，这个范围就是[l,r)[l,r)，所以循环的条件就是l<r

根据f(mid)判断范围应该往哪个方向缩小

  • 如果应该往右缩小，那么l往右缩小，mid处舍弃，根据左闭右开原则，l = mid + 1不要mid
  • 如果应该往左缩小，那么r往左移动，mid处舍弃，根据左闭右开原则，r = mid不要mid

最后循环退出，[l,r)[l,r)区间内只有一个值，就是l，故return l

例题

寻找两个正序数组的中位数

中位数只能在其中一个数组中，则需要快速判断a数组中的某个数在b数组中排第几个，并且a里的这个数不是每个都算，而是二分找到最靠中间的那个，所以这个题就是二分套二分

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

func findNumInArray(x int, arr []int) (idx int) {
	l, r := 0, len(arr)
	for r-l > 0 {
		mid := int(uint(r+l) >> 1)
		if arr[mid] < x {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}
func findMedianOfArray(nums []int) float64 {
	if len(nums)%2 == 1 {
		return float64(nums[len(nums)/2])
	}
	return float64(nums[len(nums)/2]+nums[len(nums)/2-1]) / 2
}
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	len1, len2 := len(nums1), len(nums2)
	if len1 == 0 {
		return findMedianOfArray(nums2)
	}
	if len2 == 0 {
		return findMedianOfArray(nums1)
	}
	totalLength := len1 + len2
	var oddLength = totalLength&1 == 1
	halfLength := totalLength / 2
	l := 0
	r := len1
	i := 0
	numbersInLeft := 0
	for r-l > 0 {
		mid := (l + r) >> 1
		n := nums1[mid]
		i = findNumInArray(n, nums2)
		numbersInLeft = mid + i
		if numbersInLeft < halfLength {
			l = mid + 1
		} else {
			r = mid
		}
	}
	if l >= len1 {
		if oddLength {
			return float64(nums2[halfLength-len1])
		} else {
			var a, b int
			if halfLength-len1-1 < 0 {
				a, b = nums1[len1-1], nums1[len1-1]
			} else {
				a, b = nums2[halfLength-len1-1], nums1[len1-1]
			}
			if a < b {
				a, b = b, a
			}
			return float64(nums2[halfLength-len1]+a) / 2
		}
	}
	i = findNumInArray(nums1[l], nums2)
	numbersInLeft = l + i
	if numbersInLeft == halfLength {
		if oddLength {
			return float64(nums1[l])
		}
		a, b := -1_000_000_0, -1_000_000_0
		if l > 0 {
			a = nums1[l-1]
		}
		if i > 0 {
			b = nums2[i-1]
		}
		if a < b {
			a, b = b, a
		}
		if a == -1_000_000_0 {
			a = nums2[i]
		}
		return (float64(a) + float64(nums1[l])) / 2
	} else {
		return findMedianSortedArrays(nums2, nums1)
	}
}