Leetcode面试经典150题刷题记录 —— 二分查找篇

Leetcode面试经典150题刷题记录-系列
Leetcod面试经典150题刷题记录——数组 / 字符串篇
Leetcod面试经典150题刷题记录 —— 双指针篇
Leetcod面试经典150题刷题记录 —— 矩阵篇
Leetcod面试经典150题刷题记录 —— 滑动窗口篇
Leetcod面试经典150题刷题记录 —— 哈希表篇
Leetcod面试经典150题刷题记录 —— 区间篇
Leetcod面试经典150题刷题记录——栈篇
Leetcod面试经典150题刷题记录——链表篇
Leetcod面试经典150题刷题记录——二叉树篇
Leetcod面试经典150题刷题记录——二叉树层次遍历篇
Leetcod面试经典150题刷题记录——二叉搜索树篇

1. 搜索插入位置

题目链接：搜索插入位置 - leetcode
题目描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
题目归纳：
无

解题思路：
解法： 搜索插入位置 - leetcode官方题解

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2# 此条件不成立时，有nums[mid] >= target，此时left即正确下标if nums[mid] < target: left = mid + 1else:right = mid - 1return left

2. 搜索二维矩阵

题目链接：搜索二维矩阵 - leetcode
题目描述：
给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false
题目归纳：
无

解题思路：
解法： 搜索二维矩阵 - leetcode官方题解

class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:row = self.binarySearchFirstRow(matrix, target)print(row)if row < 0:return Falsereturn self.binarySearch(matrix[row], target)def binarySearchFirstRow(self, matrix: List[List[int]], target: int) -> int:top, bottom = 0, len(matrix) - 1while top < bottom:mid = top + (bottom - top + 1) // 2 # 这样mid会更偏向bottom，从而可以最终使top = bottom使循环终止if matrix[mid][0] <= target:top = mid # 由于top不存在+1操作，所以不能用top <= bottom，很可能top一直等于bottomelse:bottom = mid - 1return topdef binarySearch(self, array:List[int], target):left, right = 0, len(array) - 1while left <= right:mid = left + (right - left) // 2if array[mid] == target:return Trueelif array[mid] < target:left = mid + 1elif array[mid] > target:right = mid - 1return False

关于二分查找的下标和写法问题，请看文章[1]

参考文章与视频链接
[1]数据结构与算法 —— 常用算法模版