转化方式：

>=x 使用sort.SearchInts(nums, x)
>x 使用 sort.SearchInts(nums, x+1)
<x 使用sort.SearchInts(nums, x) -1
<= 使用sort.SearchInts(nums, x +1) -1

704 二分查找

704. 二分查找 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func search(nums []int, target int) int {
    left, right := 0, len(nums)-1

    for left <= right {
        mid := left + (right - left)/ 2
        if nums[mid] > target {
            right = mid - 1
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            return mid
        }
    }
    return -1
}

2529. 正整数和负整数的最大计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

func maximumCount(nums []int) int {
	// 返回反照非低价顺序排列的数组 nums ， 返回正整数数目和负整数数目中的最大值
	// pos neg pos neg max

	// 获得 >0 =》 >= target + 1 ;  <0   >=(target) -1
    
    // 负整数个数：第一个大于等于0的索引位置（即所有小于0的元素数量）
    negCount := sort.SearchInts(nums, 0)
    
    // 正整数个数：总长度减去第一个大于等于1的索引位置
    posCount := n - sort.SearchInts(nums, 1)
    
    if negCount > posCount {
        return negCount
    }
    return posCount
}


1385. 两个数组间的距离值

1
2
3
4
5
6
7
8
9
10
11
12

func findTheDistanceValue(arr1, arr2 []int, d int) (ans int) {
    sort.Ints(arr2)
    for _, x := range arr1 {
        i := sort.SearchInts(arr2, x - d) // 
        if i == len(arr2) || arr2[i] > x + d { // 不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d， 即都不在[x - d, x + d] 之间， 所以不能使用arr2[i] >= x + d
            ans++
        }
    }
    return 
}

153. 寻找旋转排序数组中的最小值

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

func findMin(nums []int) int {
    left, right := 0, len(nums)-1  // 左闭右闭区间 [left, right]
    for left < right {             // 终止条件：left == right
        mid := left + (right-left)/2
        if nums[mid] < nums[len(nums)-1] {
            right = mid           // 最小值在 [left, mid]
        } else {
            left = mid + 1       // 最小值在 [mid + 1, right]
        }
    }
    return nums[left]             // 此时 left == right，指向最小值
}


func findMin(nums []int) int {
    left, right := -1, len(nums) -1 // 左开右闭区间 (left, right]
    for left+1 < right {
        mid := left + (right - left) /2
        if nums[mid] < nums[len(nums)-1] {
            right = mid
        } else {
            left = mid
        }
       
    }
    return nums[right]
}

33. 搜索旋转排序数组

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

func search(nums []int, target int) int {
    end := nums[len(nums)-1]
    check := func(i int) bool {
        x := nums[i]
        if x > end {
            return target > end && x >= target
        }
        return target > end || x >= target
    }

    left, right := -1, len(nums)-1 // 开区间 (-1, n-1)
    for left+1 < right { // 开区间不为空
        mid := left + (right-left)/2
        if check(mid) {
            right = mid
        } else {
            left = mid
        }
    }
    if nums[right] != target {
        return -1
    }
    return right
}

TODO