Week 10 @ 2025 算法周记【二分搜索】

1 二分搜索

二分搜索

LC 704. Binary Search 二分查找

https://leetcode.com/problems/binary-search/description/?show=1

func search(nums []int, target int) int {
    L, R := 0, len(nums)
    for L < R {
        mid := L + (R - L) / 2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            L = mid + 1
        } else {
            R = mid
        }
    }

    return -1
}

LC 34. Find First and Last Position of Element in Sorted Array 在排序数组中找元素的第一个和最后一个位置

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/?show=1

func searchRange(nums []int, target int) []int {
    LB := leftBound(nums, target)
    if LB == len(nums) || nums[LB] != target {
        return []int{-1, -1}
    }
    UB := leftBound(nums, target + 1) - 1

    return []int{LB, UB}
}

func leftBound(nums []int, target int) int {
    L, R := 0, len(nums)
    for L < R {
        mid := L + (R - L) / 2
        if nums[mid] < target {
            L = mid+1
        } else {
            R = mid
        }
    }
    return R
}

LC 875. Koko Eating Bananas 爱吃香蕉的珂珂

https://leetcode.com/problems/koko-eating-bananas/description/

func minEatingSpeed(piles []int, h int) int {
    L, R := 1, 1_000_000_001

    for L < R {
        mid := L + (R-L)/2

        if getCount(piles, mid) <= h {
            R = mid
        } else {
            L = mid + 1
        }
    }

    return R
}

func getCount(piles []int, k int) int {
    c := 0

    for _, x := range piles {
        c += x / k
        if x % k != 0 {
            c++
        }
    }

    return c
}

LC 1011. Capacity To Ship Packages Within D Days 在 D 天内送达包裹的能力

https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/description/

func shipWithinDays(weights []int, days int) int {
    L, R := getInit(weights)

    for L < R {
        mid := L + (R - L) / 2

        if getNeedDays(weights, mid) <= days {
            R = mid
        } else {
            L = mid + 1
        }
    }

    return R
}

func getInit(arr []int) (L, R int) {
    L, R = 0, 1
    for _, x := range arr {
        L = max(L, x)
        R += x
    }
    return
}

func getNeedDays(weights []int, cap int) (days int) {
    remain := 0
    for _, w := range weights {
        if remain < w {
            remain = cap
            days++
        }

        remain -= w
    }

    return
}

LC 410. Split Array Largest Sum 分割数组的最大值

https://leetcode.com/problems/split-array-largest-sum/description/

func splitArray(nums []int, k int) int {
    L, R := getInit(nums)

    for L < R {
        mid := L + (R - L) / 2

        if getSplitsCount(nums, mid) <= k {
            R = mid
        } else {
            L = mid + 1
        }
    }

    return R
}


func getInit(arr []int) (L, R int) {
    L, R = 0, 1
    for _, x := range arr {
        L = max(L, x)
        R += x
    }
    return
}


func getSplitsCount(nums []int, maxGroupSum int) (c int) {
    remain := 0
    for _, num := range nums {
        if remain < num {
            remain = maxGroupSum
            c++
        }

        remain -= num
    }

    return
}

LC 566. Reshape the Matrix 重塑矩阵

https://leetcode.com/problems/reshape-the-matrix/description/

func matrixReshape(mat [][]int, r int, c int) [][]int {
    m, n := len(mat), len(mat[0])
    if m * n != r * c { // invalid
        return mat
    }

    newMatrix := createMatrix(r, c)

    i, j := 0, 0
    next := func() {
        j++
        if j >= c {
            i++
            j = 0
        }
    }

    for _, row := range mat {
        for _, v := range row {
            newMatrix[i][j] = v
            next()
        }
    }

    return newMatrix
}

func createMatrix(m, n int) [][]int {
    mat := make([][]int, m)
    for i := range mat {
        mat[i] = make([]int, n)
    }
    return mat
}

转换坐标

func matrixReshape(mat [][]int, r int, c int) [][]int {
    n := len(mat[0])
    // 如果想成功 reshape，元素个数应该相同
    if r*c != len(mat)*n {
        return mat
    }

    res := make([][]int, r)
    for i := range res {
        res[i] = make([]int, c)
    }
    
    for i := 0; i < len(mat)*n; i++ {
        set(&res, i, get(&mat, i, n))
    }
    return res
}

// 通过一维坐标访问二维数组中的元素
func get(matrix *[][]int, index int, n int) int {
    // 计算二维中的横纵坐标
    i := index / n
    j := index % n
    return (*matrix)[i][j]
}

// 通过一维坐标设置二维数组中的元素
func set(matrix *[][]int, index int, value int) {
    n := len((*matrix)[0])
    // 计算二维中的横纵坐标
    i := index / n
    j := index % n
    (*matrix)[i][j] = value
}

LC 74. Search a 2D Matrix 搜索二维矩阵

https://leetcode.com/problems/search-a-2d-matrix/description/

func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])

    getValueByIndex := func(index int) int {
        i := index / n
        j := index % n
        return matrix[i][j]
    }

    L, R := 0, m*n
    for L < R {
        mid := L + (R - L) / 2

        midValue := getValueByIndex(mid)
        if midValue == target {
            return true
        } else if midValue < target {
            L = mid + 1
        } else {
            R = mid
        }
    }

    return false
}