二分查找

Posted on Edited on In Word count in article: 4.1k Reading time ≈ 4 mins.
二分查找

二分查找条件：

1.目标函数单调性，递增或者递减

2.存在上下界

3.能够通过索引访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 二分查找
func two(nums []int) int {
	// 左右起点
	left, right := 0, len(nums) - 1
	for left <= right {
		// 得到中间值
		mid = left + (right - left) >> 1
		// 等于找到则返回
		if nums[mid] == target {
			return target or break
		} else if mid < target { // 否则target在mid右侧，左下标到mid+1
			left = mid + 1
		} else { // target在mid左侧，右下标到mid-1
			right = mid - 1
		}
	}


每次循环将搜索范围缩小到之前的一半， O（logN）

PS：
1.计算 mid 时 ，不能使用 （left + right ）/ 2,否则有可能会导致溢出

2.for循环结束条件是 left <= right， left=right正是最终结果，不能漏掉

3.left = mid + 1,right = mid - 1 而不是 left = mid 和 right = mid

例题

半有序数组

使用二分查找，寻找一个半有序数组中间无序的地方[4,5,6,7,0,1,2]

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
// 二分查找，返回的是数组的索引
func search(nums []int) int {
	// 边界条件
    if len(nums) < 2 {
        return 0
    }
    // 左右下标
    l := 0
    r := len(nums) - 1
    for l <= r {
        mid := (l + r) / 2
        // 最后左右相等的时候就是转折
        if l == r {
            return l
        }
        // 如果左边小于中间值，左半部分递增，则转折点在右边，否在在左边
        if nums[r] < nums[mid] {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return 0
}

// 暴力法
func search(nums []int) int {
	// 边界条件
    if len(nums) < 2 {
        return 0
    }
    for i, v := range nums {
    	// 出现转折，说明下一个值小于前一个值了
        if v > nums[i+1] {
            return i
        }
    }
    return 0
}

该题类似搜索旋转数组，搜索旋转数组，是要寻找目标值，则在二分查找时，进行数值比对，根据比对不同情况，对左右下标的不同处理

有效的完全平方数

二分查找方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 二分查找
func isPerfectSquare(num int) bool {
	// 边界条件
    if num < 2 {
        return true
    }
    l := 0
    // 平方根一定在一半之前，后面的平方肯定大于num
    r := num / 2
    for l <= r {
        mid := (l + r) / 2
        // 找到结果返回
        if mid * mid == num { return true }
        if mid * mid > num { 
            r = mid - 1
        } else {l = mid + 1}
    }
    return false
}

奇数方法
完全平方数都是由奇数组成的，每次减去奇数，最后是0则是完全平方数

1
2
3
4
5
6
7
8
func isPerfectSquare(num int) bool {
    n := 1
    for num > 0 {
        num -= n
        n += 2
    }
    return num == 0
}

牛顿迭代

以当前点的切线斜率公式推导 x^2 - num = 0

当前点的切线交于x轴为y点

f(x)/(x - y) = f`(x)

(x^2 - num)/(x-y) = 2x

x^2 - num = 2x^2-2xy

y=(x+num/x)/2

1
2
3
4
5
6
7
8
9
10
11
12
func isPerfectSquare(num int) bool {
    if num < 2 {
        return true
    }
    // 从一半开始
    x := num / 2
    // 不断迭代，找其切线斜率的坐标，直到，满足表达式x^2 - num = 0
    for x * x > num {
        x = (x + num / x) / 2
    }
    return x * x == num
}

搜索旋转数组

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
// 二分查找，不同情况比对，特殊条件处理缩小的条件
func search(nums []int, target int) int {
    // 边界条件
    if len(nums) == 1 {
        if target == nums[0] {
            return 0
        } else {
            return -1
        }
    }
    // 左右下标
    l := 0
    r := len(nums) - 1
    for l <= r {
        mid := (l + r) / 2
        // 等于目标值返回索引
        if nums[mid] == target {
            return mid
        }
        // 分四种情况
        // 左边小于中间，说明左边升序，旋转在右边
        if nums[l] <= nums[mid]  {
            // target在左边，则往左边缩小
            if target >= nums[l] && target <= nums[mid] {
                r = mid - 1
            } else { // 否则右边缩小
                l = mid + 1
            }
        // 否则右边升序
        } else {
            // target在右边，往右边缩小，否则左边
            if target >= nums[mid] && target <= nums[r] {
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
    }
    return -1 
}

// 如果数组包含重复数字，搜索旋转数组二
func search(nums []int, target int) bool {
    if len(nums) == 1 {
        if target == nums[0] {
            return true
        }
        return false
    }
    l := 0
    r := len(nums) - 1
    for l <= r {
        mid := (l + r) / 2
        if nums[mid] == target {
            return true
        }
        // 对重复数字进行处理跳过
        if nums[l] == nums[mid] {
            l++
        } else if nums[mid] == nums[r] {
            r--
        } else if nums[l] < nums[mid] {
            if target >= nums[l] && target < nums[mid] {
                r = mid - 1
            } else {
                l = mid + 1
            }
        } else {
            if target > nums[mid] && target <= nums[r] {
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
    }
    return false
}

搜索二维矩阵数组

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
// 缩减搜索范围，先找到对应的行。然后再对该行进行二分
func searchMatrix(matrix [][]int, target int) bool {
    cur := []int{}
    for _, v := range matrix {
        if target >= v[0] && target <= v[len(v) - 1] {
            cur = v
        }
    }
    if len(cur) == 0 {
        return false
    }
    l := 0
    r := len(cur) - 1
    for l <= r {
        mid := (l + r) / 2
        if cur[mid] == target {
            return true
        }
        if cur[mid] > target {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return false
}

// 直接二分法
// 将二维数组想象成一个完整的一维数组，通过一维数字的索引，转换成二维数组的索引
// 通过一维数组的索引进行二分，每一行的个数是n，整数结果是第几行，取余是第几列
func searchMatrix(matrix [][]int, target int) bool {
    m := len(matrix)
    n := len(matrix[0])
    l := 0
    r := m * n - 1
    for l <= r {
        mid := l + (r - l) / 2
        if matrix[mid / n][mid % n] == target {
            return true
        }
        if matrix[mid / n][mid % n] > target {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return false
}