Binary search topic

Binary search

Key words: ordered array, can try to use binary search

Problem definition

Given an ordered array of numbers, nums, and given you a numeric target. Ask if target exists in NUMS. If it exists, its index in NUMS is returned. If none exists, -1 is returned

Basic binary search

Algorithm definition: to search for the key and the subarray intermediate key comparison, if the key is less than the middle key to find out, will continue to search in the left subarray, if is greater than the middle key, in the right subarray lookup, otherwise, the key is to find elements Basic algorithms require orderly array elements without repeating element The basic framework is as follows:

func binarySearch(src []int, target int) {
    for{mid = left + (right-left) >>1
        ifSRC [mid] > target {continue search in left subarray}else ifSRC [mid] < target {continue in the right subarray}else{if found, returnreturn mid
        }
    }
    return - 1
}
Copy the code

Binary search deformation

If there are repeated elements, you can also obtain the information you want by modifying the search conditions and return values. The core lies in: discard illegal values in the ordered search interval

2. The skills

Cyclic invariant

That is, each boundary is handled according to the definition of the interval

Thinking framework

First, define the search interval
Define end-of-loop conditions based on the search interval
Compare the intermediate element with the target element
According to the comparison results, the interval is shrunk and the illegitimate solution is discarded
When exiting the loop, consider the current l and R values

3. Basic template

Left and right closed interval

Define target in the range [left, right] where right is the actual value available, so always remember:

When you define right, you can take it, solen(nums)-1
When I write the for condition, I can pick the point left == right that makes sense, soleft <= right

When you update the right, you can take the right, in the previous judgment, that’s already truesrc[mid]This value has been judged, and the next round does not need to judge this position, so the next time keep the interval[left, mid-1], so right is updated to mid-1

The template as follows:

func binarySearch(nums []int, target int) int {
    // Initialization of 1.r
	l, r := 0.len(nums)- 1
	// Write the range for to remind yourself: [l,r]
	// 2. Loop conditions
	for l <= r {
		mid := l + (r-l)>>1
		if nums[mid] < target {
			l = mid + 1
		} else if nums[mid] > target {
			// change of r
			r = mid - 1
		} else {
			return mid
		}
	}
	return - 1
}
Copy the code

167. Sum of two numbers II – Enter ordered array

// Double pointer + binary
// The left pointer traverses one by one, and the right pointer divides to find the difference
func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        if idx := binarySearch(nums[i+1:], target - nums[i]); idx ! =- 1 {
            return []int{i+1, idx+(i+1) +1}}}return []int{}}// Find the insertion position
func binarySearch(nums []int, target int) int {
    l, r := 0.len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] > target {
            r = mid - 1
        } else if nums[mid] < target {
            l = mid + 1
        } else {
            return mid
        }
    }
    return - 1
}
Copy the code

367. Valid perfect squares

func isPerfectSquare(num int) bool {
    l, r := 1, num
    for l <= r {
        mid := l + (r-l) >> 1
        if mid * mid == num {
            return true
        } else if mid * mid < num {
            l = mid + 1
        } else {
            r = mid - 1}}return false
}
Copy the code

374. Guess the number size

/** * Forward declaration of guess API. * @param num your guess * @return -1 if num is lower than the guess number * 1 if num is higher than the guess number * otherwise return 0 * func guess(num int) int; * /

func guessNumber(n int) int {
    l, r := 1, n
    for l <= r {
        mid := l + (r-l) >> 1
        cmp := guess(mid)
        if cmp == - 1 {
            r = mid - 1
        } else if cmp == 1 {
            l = mid + 1
        } else {
            return mid
        }
    }
    return - 1
}
Copy the code

4. Common deformation

1. Find the leftmost value that meets the condition

Num [mid] == target mid == 0,1,1,1,2,3,4 Let’s go further to the left and see if there’s a better solution and maybe L crosses the boundary, so you have to decide if l crosses the boundary before you jump out

func binarySearch(nums []int, target int) int {
    l, r := 0.len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        // We also need to look to the left
        if nums[mid] >= target {
            r = mid - 1
        } else {
            l = mid + 1}}Len (nums) >= len(nums)
    if l >= len(nums) || nums[l] ! = target {return - 1
    }
    // Since equality is to the left, the reduced r, l is the spare tire, and finally returns L
    return l
}
Copy the code

1351. Count the negative numbers in ordered matrices

Select * from the right of the array where target = 0. Select * from the right of the array where target = 0. Select * from the right of the array where target = 0

// Find the rightmost range where target is 0
func countNegatives(grid [][]int) int {
    ans := 0
    for _, src := range grid {
        idx := binarySearch(src, 0)
        ans += len(src) - idx
    }
    return ans
}
func binarySearch(src []int, target int) int {
    // [l, r]
    l, r := 0.len(src) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if src[mid] < target {
            r = mid - 1
        } else {
            l = mid + 1}}return l
}
Copy the code

69. Square root of x

Square root special treatment, small is likely to be the answer, so record the following in advance

func mySqrt(x int) int {
    // [l, r]
    l, r := 0, x
    ans := 0
    for l <= r {
        mid := l + (r-l) >> 1
        if mid * mid > x {
            r = mid - 1
        } else if mid * mid == x {
            return mid
        } else {
            ans = mid
            l = mid + 1}}return ans
}
Copy the code

278. The first incorrect version

When true is returned, continue to the left to see if there is a more suitable solution

/** * Forward declaration of isBadVersion API. * @param version your guess about first bad version * @return true if current version is bad * false if current version is good * func isBadVersion(version int) bool; * /

func firstBadVersion(n int) int {
    l, r := 1, n
    for l <= r {
        mid := l + (r-l) >> 1
        if isBadVersion(mid) {
            r = mid - 1
        } else {
            l = mid + 1}}return l
}
Copy the code

441. Arrange coins

Similar to finding the square root, you might get lost looking for smaller values, so make a note of that

func arrangeCoins(n int) int {
    l, r := 1, n
    ans := 0
    for l <= r {
        mid := l + (r-l) >> 1
        sum := (1 + mid) * mid / 2
        if sum <= n {
            ans = mid
            l = mid + 1
        } else {
            r = mid - 1}}return ans
}
Copy the code

875. Coco who loves bananas

/* dichotomous, the velocity interval is [1,sum] to find the leftmost satisfy the condition */
func minEatingSpeed(piles []int, h int) int {
    sum := 0
    for _, v := range piles {
        sum += v
    }
    l, r := 1, sum
    for l <= r {
        mid := l + (r-l) >> 1
        if check(piles, h, mid) {
            r = mid - 1
        } else {
            l = mid + 1}}return l
}
func check(piles []int, h, speed int) bool {
    hour := 0
    for _, v := range piles {
        hour += int(math.Ceil(float64(v)/float64(speed)))
    }
    return hour <= h
}
Copy the code

2. Find the rightmost value that meets the condition

Similar to finding the leftmost value that satisfies the condition, when the value is equal, you can go to the right and see if there is a template like this:

func binarySearch(nums []int, target int) int {
    l, r := 0.len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        // Let's go to the right
        if nums[mid] <= target {
            l = mid + 1
        } else {
            r = mid - 1}}// If r < 0, r < 0, r < 0
    if r < 0|| nums[r] ! = target {return - 1
    }
    // Since equality is to the right, l changes and r is the spare tire
    return r
}
Copy the code

Find the difference between the left-most and right-most satisfiers:

When they’re equal, they’re different, so if you look to the left, you go to the left, and if you look to the right, you go to the right
Due to different spare tires, the judgment after jumping out is also for different spare tires, so the range is different
The spare tire that returns at the end is also different

34. Find the first and last positions of elements in a sorted array

// find the most left and most right to satisfy the condition
func searchRange(nums []int, target int) []int {
    if len(nums) == 0 {
        return []int{- 1.- 1}
    }
    left := LeftBinarySearch(nums, target)
    right := rightBinarySearch(nums, target)
    return []int{left, right}
}
func LeftBinarySearch(nums []int, target int) int {
    l, r := 0.len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] >= target {
            r = mid - 1
        } else {
            l = mid + 1}}if l >= len(nums) || nums[l] ! = target {return - 1
    }
    return l
}
func rightBinarySearch(nums []int, target int) int {
    l, r := 0.len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] > target {
            r = mid - 1
        } else {
            l = mid + 1}}if r < 0|| nums[r] ! = target {return - 1
    }
    return r
}
Copy the code

3. Find the leftmost insertion position

In the array [1,2,4], target is 3. If target is not found, return the target where it should be inserted, so that the array is still in order. If there are more than one value, return the leftmost value, such as [1,4,4,4,4,4], target is 4, and should be inserted at 1. That is greater than or equal to the number of values can be a “spare tire”, the answer when it comes to “spare tire”, need to continue to look to the left again is there a more appropriate solution Finally jump out of the loop, l is the current best spare tire, return the l can Jump out of the loop, the meaning of l is “less than want to insert the number of values” (to find the right insert position in the same way)

func binarySearch(nums []int, target int) int {
	// Initialization of 1.r
	l, r := 0.len(nums)- 1
	// Write the range for to remind yourself: [l,r]
	// 2. Loop conditions
	for l <= r {
		mid := l + (r-l)>>1
        // Greater than or equal to this number, continue to the left to find the spare tire
		if nums[mid] >= target {
			// change of r
			r = mid - 1
		} else {
			l = mid + 1}}// l is the best backup
	return l
}
Copy the code

35. Search for insertion locations

Just like the template

func searchInsert(nums []int, target int) int {
    // [l, r]
    l, r := 0.len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] >= target {
            r = mid - 1
        } else {
            l = mid + 1}}return l
}
Copy the code

744. Find the smallest letter larger than the target letter

// Find the value of the rightmost insertion position
// Special point: if equal to, go to the right
func nextGreatestLetter(letters []byte, target byte) byte {
    l, r := 0.len(letters)
    for l < r {
        mid := l + (r-l) >> 1
        if letters[mid] <= target {
            l = mid + 1
        } else {
            r = mid
        }
    }
    // l means "less than or equal to the number of inserts"
    return letters[l%len(letters)]
}
Copy the code

Find K closest elements

// Find the leftmost insertion position, then go to both sides to find enough numbers
func findClosestElements(arr []int, k int, x int) []int {
    ans := make([]int.0, k)
    // Res may differ by 0 from x, or it may differ by more
    res := search(arr, x)
    l, r := res- 1, res
    for len(ans) < k {
        / / on the left
        if l >= 0 && (r == len(arr) || abs(arr[l]-x) <= abs(arr[r]-x)) {
            ans = append(ans, arr[l])
            l--
        } else {
            // Otherwise add the right side
            ans = append(ans, arr[r])
            r++
        }
    }
    // The result is sorted
    sort.Ints(ans)
    return ans
}
func search(nums []int, target int) int {
    l, r := 0.len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] >= target {
            r = mid - 1
        } else {
            l = mid + 1}}return l
}
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}
Copy the code

4. Local order

The problem is that, when looking for a value in a locally ordered array, the array may fall before it rises, or rise before it falls, for example, [5,6,7,1,2,3,4], in which case you need to compare which part of the array is preceded by the current [l,r] interval. In fact, we can also help judge what the current search interval is by using conditions such as ARR [L], ARR [R], ARR [0], ARR [Len (ARR)-1], ARR [mid-1], ARR [mid+1]. According to the analysis of the situation, which half of the illegal solutions need to be abandoned, we can find an orderly interval and make judgment in the orderly interval

33. Search rotation sort array

func search(nums []int, target int) int {
    l, r := 0.len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] == target {
            return mid
        } else if nums[l] <= nums[mid] {
            // target in [l, mid], cut the bottom part
            if nums[l] <= target && target < nums[mid] {
                r = mid - 1
            } else {
                l = mid + 1}}else {
             // target in (mid, r), cut the first part
            if nums[mid] < target && target <= nums[r] {
                l = mid + 1
            } else {
                r = mid - 1}}}return - 1
}
Copy the code

81. Search rotated sorted array II

There may be duplicates and interference can only be eliminated item by item

func search(nums []int, target int) bool {
    l, r := 0.len(nums) - 1
    for l <= r {
        mid := l + (r-l) >> 1
        if nums[mid] == target {
            return true
        }
        // There is no way to eliminate the interference items by traversing them
        for l < mid && nums[l] == nums[mid] {
            l++
        }
        if nums[l] <= nums[mid] {
            if nums[l] <= target && target < nums[mid] {
                r = mid - 1
            } else {
                l = mid + 1}}else {
            if nums[mid] < target && target <= nums[r] {
                l = mid + 1
            } else {
                r = mid - 1}}}return false
}
Copy the code

5. Look for the best value

To find the maximum value in dichotomy, it is necessary to always set the maximum value within the interval and constantly shrink the left and right boundaries. Even if the maximum value is found, it must be at least in order within the range

Find the minimum value in the rotation sort array

L, R, mid (position) values can only be in three cases:

L is minimum, for example [1,2,3], l < mid, mid < r, shrink right
For example, [3,1,2], l > mid, mid < r, shrink the right side, but can not shrink mid
R is minimum, e.g. [2,3,1], l < mid, mid > r, shrink left

If I select mid > r, if I go to the left side, if I don’t go to the right side, I can’t shrink mid, so I have to shrink r = mid. When there is only one search interval left, I will keep shrinking the right side, so r = L, and r stays the same, so the loop condition can only be L < r, In addition, the search interval is the minimum value, so return nums[l] as nums[r]

func findMin(nums []int) int {
    l, r := 0.len(nums) - 1
    for l < r {
        mid := l + (r-l) >> 1
        if nums[mid] > nums[r] {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return nums[l]
}
Copy the code

162. Look for peaks

If you have left and right pockets, you can always find the best value if you go along a slope

func findPeakElement(nums []int) int {
    l, r := 0.len(nums) - 1
    for l < r {
        mid := l + (r-l) >> 1
        if nums[mid] > nums[mid+1] {
            r = mid
        } else {
            l = mid + 1}}return l
}
Copy the code

852. Peak index of the mountain array

The question is, if you want to figure out if you’re going uphill or downhill, mid and mid+1, if you’re going uphill, you’re going to have a peak

func peakIndexInMountainArray(arr []int) int {
    l, r := 0.len(arr) - 1
    for l < r {
        mid := l + (r-l) >> 1
        if arr[mid] > arr[mid+1] {  / / downhill
            r = mid 
        } else {
            l = mid + 1}}return l
}
Copy the code