第 3 章 常用算法3.1 查找算法3.1.1 二分查找适用于 排好序的1)算法原理二分查找又称折半查找适用于有序列表。其利用数据的有序性每轮缩小一半搜索范围直至找到目标元素或搜索区间为空为止。2)代码实现def binary_search(arr, target): left, right 0, len(arr) - 1 while left right: mid left (right - left) // 2 # mid left (right - left) //2 #第二种方式,python为弱语言,不需要这么写,但java需要避免越界 if arr[mid] target: return mid # 找到目标值返回索引 elif arr[mid] target: left mid 1 # 目标值在右半部分 else: right mid - 1 # 目标值在左半部分 return -1 # 未找到目标值3)复杂度分析时间复杂度在循环中区间每轮缩小一半因此时间复杂度为O(logn)。空间复杂度使用常数大小的额外空间空间复杂度为O(1)。3.1.2 查找多数元素力扣169题https://leetcode.cn/problems/majority-element/description/返回数组中数量超过半数的元素要求时间复杂度O(n)、空间复杂度O(1)。示例输入nums [2,2,1,1,1,2,2]输出21)思路分析为了严格符合复杂度要求可以使用多数投票算法多数投票算法也叫摩尔投票算法。摩尔投票算法的核心思想是对立性和抵消它基于这样一个事实如果一个元素在数组中出现的次数超过数组长度的一半那么在不断消除不同元素对的过程中这个多数元素最终会留下来。具体来说算法维护两个变量一个是候选元素 candidate另一个是该候选元素的计数 count。在遍历数组的过程中遇到与候选元素相同的元素时计数加 1遇到不同的元素时计数减 1。当计数减为 0 时说明当前候选元素被抵消完需要更换候选元素为当前遍历到的元素并将计数重置为 1。算法步骤初始化选择数组的第一个元素作为初始候选元素 candidate。将计数 count 初始化为 1。遍历数组从数组的第二个元素开始遍历。若当前元素与候选元素相同count 加 1。若当前元素与候选元素不同count 减 1。当 count 变为 0 时将当前元素设为新的候选元素并将 count 重置为 1。返回结果遍历结束后candidate 即为多数元素。代码实现def majorityElement(nums): # 初始化候选元素为数组的第一个元素 candidate nums[0] # 初始化候选元素的票数为 1 count 1 # 从数组的第二个元素开始遍历 for num in nums[1:]: if num candidate: # 如果当前元素与候选元素相同票数加 1 count 1 else: # 如果当前元素与候选元素不同票数减 1 count - 1 if count 0: # 当票数为 0 时更新候选元素为当前元素并将票数重置为 1 candidate num count 1 return candidate # 测试示例 nums [2, 2, 1, 1, 1, 2, 2] print(majorityElement(nums))