二分搜索.md

二分搜索

模板

给一个有序数组和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回-1

模板四点要素

1. 初始化：start=0、end=len-1
2. 循环退出条件：start + 1 < end
3. 比较中点和目标值：A[mid] ==、 <、> target
4. 判断最后两个元素是否符合：A[start]、A[end] ? target

时间复杂度 O(logn)，使用场景一般是有序数组的查找。

典型例子

704. 二分查找

func search(nums []int, target int) int {
    // 1. 初始化：start、end
    start := 0
    end := len(nums) - 1

    // 2. 处理 for 循环
    for start + 1 < end {
        mid := start + (end - start) / 2
        // 比较中点和目标值：A[mid] ==、 <、> target
        if nums[mid] == target {
            end = mid
        } else if nums[mid] < target {
            start = mid
        } else if nums[mid] > target {
            end = mid
        }
    }

    // 4、最后剩下两个元素，手动判断
    if nums[start] == target {
        return start
    }
    if nums[end] == target {
        return end
    }
    return -1
}

这 3 个模板的不同之处在于：

• 左、中、右索引的分配；
• 循环或递归终止条件；
• 后处理的必要性；

模板 #1 (left <= right)

• 二分查找的最基础和最基本的形式；
• 查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）；
• 不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

模板 #2 (left < right)

• 一种实现二分查找的高级方法；
• 查找条件需要访问元素的直接右邻居；
• 使用元素的右邻居来确定是否满足条件，并决定是向左还是向右；
• 保证查找空间在每一步中至少有 2 个元素；
• 需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

模板 #3 (left + 1 < right)

1. 实现二分查找的另一种方法；
2. 搜索条件需要访问元素的直接左右邻居；
3. 使用元素的邻居来确定它是向右还是向左；
4. 保证查找空间在每个步骤中至少有 3 个元素；
5. 需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。

例题

35. 搜索插入位置

func searchInsert(nums []int, target int) int {
    start := 0
    end := len(nums) - 1
    
    for start + 1 < end {
        mid := start + (end - start) / 2
        if nums[mid] <= target {
            start = mid
        } else {
            end = mid
        }
    }
    if nums[start] >= target {
        return start
    } else if nums[end] >= target {
        return end
    } else if nums[end] < target {
        return end + 1
    }
    return 0
}

74. 搜索二维矩阵

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

    start := 0
    end := m * n - 1

    for start + 1 < end {
        mid := start + (end - start) / 2
        x, y := changeLocation(mid, n)
        if matrix[x][y] == target {
            end = mid
        } else if matrix[x][y] < target {
            start = mid
        } else {
            end = mid
        }
    }
    x, y := changeLocation(start, n)
    if matrix[x][y] == target {
        return true
    }
    x, y = changeLocation(end, n)
    if matrix[x][y] == target {
        return true
    }
    return false
}

func changeLocation(index, n int) (int, int) {
    x := index / n
    y := index % n
    return x, y
}

278. 第一个错误的版本

func firstBadVersion(n int) int {
    low := 1
    high := n

    for low < high {
        mid := low + (high - low) / 2
        if isBadVersion(mid) {
            high = mid
        } else {
            low = mid + 1
        }
    }
    return low
}

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

func findMin(nums []int) int {
    if len(nums) == 0 {
        return -1
    }

    start := 0
    end := len(nums) - 1

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

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

func findMin(nums []int) int {
    if len(nums) == 0 {
        return -1
    }

    start := 0
    end := len(nums) - 1

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

33. 搜索旋转排序数组

func search(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }
    n := len(nums)
    start := 0
    end := n - 1

    minIndex := findMin(nums)
    sortedNums := append(nums[minIndex:], nums[:minIndex]...)
    fmt.Println(sortedNums, minIndex)

    for start + 1 < end {
        mid := start + (end - start) / 2
        if sortedNums[mid] <= target {
            start = mid
        } else if sortedNums[mid] > target {
            end = mid
        }
    }
    if sortedNums[start] == target {
        return (start + minIndex) % n
    }
    if sortedNums[end] == target {
        return (end + minIndex) % n
    }
    return -1
}

func findMin(nums []int) int {
    if len(nums) == 0 {
        return -1
    }

    start := 0
    end := len(nums) - 1

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

func search(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }

    start := 0
    end := len(nums) - 1

    for start + 1 < end {
        mid := start + (end - start) / 2
        if nums[mid] == target {
            return mid
        }

        if nums[start] < nums[mid] {
            if nums[start] <= target && target <= nums[mid] {
                end = mid
            } else {
                start = mid
            }
        } else if nums[end] > nums[mid] {
            if nums[end] >= target && nums[mid] <= target {
                start = mid
            } else {
                end = mid
            }
        }
    }
    
    if nums[start] == target {
        return start
    } else if nums[end] == target {
        return end
    }
    return -1
}

81. 搜索旋转排序数组 II

func search(nums []int, target int) bool {
    if len(nums) == 0 {
        return false
    }

    start := 0
    end := len(nums) - 1

    for start + 1 < end {

        for start < end && nums[start] == nums[start+1] {
            start++
        }
        for start < end && nums[end] == nums[end-1] {
            end--
        }
        
        mid := start + (end - start) / 2
        if nums[mid] == target  {
            return true
        }

        if nums[start] < nums[mid] {
            if nums[start] <= target && target <= nums[mid] {
                end = mid
            } else {
                start = mid
            }
        } else if nums[end] > nums[mid] {
            if nums[end] >= target && nums[mid] <= target {
                start = mid
            } else {
                end = mid
            }
        }
    }

    if nums[start] == target || nums[end] == target {
        return true
    }
    return false
}