当前位置: 首页 > news >正文

Python世界:力扣题704二分查找

Python世界:力扣题704二分查找

    • 任务背景
    • 思路分析
    • 代码实现
    • 测试套件
    • 本文小结

任务背景


问题来自力扣题目704:Binary Search,大意如下:

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

翻译下,需求是:对有序数组进行查找指定数字,若有返回索引,若无返回-1.

思路分析


重温下二分写法,思路很简单,发现值大的下移上界,发现值小的上移下界,直到上下界重合。

要注意的是无target时,mid的偏移问题。

代码实现


class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""# range: [low, high)low = 0high = len(nums)while (low < high):mid = low + (high - low) // 2if nums[mid] < target:low = mid + 1elif nums[mid] > target:high = midelse:return mid# not foundreturn -1# test
nums = [-1, 0, 3, 5, 9, 12]
target = 9# nums = [-1,0,3,5,9,12]
# target = 2sol = Solution()
res = sol.search(nums, target)
print(res)

测试套件


# 导入单元测试
import unittest# 编写测试套
class TestSol(unittest.TestCase):# 不在数组中def test_special1(self):nums = [-1, 0, 3, 5, 9, 12]target = 2ret = -1sol = Solution()self.assertEqual(sol.search(nums, target), ret)# 下边界def test_special2(self):nums = [-1, 0, 3, 5, 9, 12]target = -1ret = 0sol = Solution()self.assertEqual(sol.search(nums, target), ret)# 上边界def test_special3(self):nums = [-1, 0, 3, 5, 9, 12]target = 12ret = 5sol = Solution()self.assertEqual(sol.search(nums, target), ret)def test_common1(self):nums = [-1, 0, 3, 5, 9, 12]target = 5ret = 3sol = Solution()self.assertEqual(sol.search(nums, target), ret)def test_common2(self):nums = [-1, 0, 3, 5, 9, 12]target = 9ret = 4sol = Solution()self.assertEqual(sol.search(nums, target), ret)# 含测试套版本主调
if __name__ == '__main__':print('start!')unittest.main() # 启动单元测试print('done!')

本文小结


二分核心:索引偏移存乎一心。

可进一步思考若有重复值时,如何找到最小重复索引或最大重复索引。

http://www.lryc.cn/news/480228.html

相关文章:

  • W55RP20-EVB-Pico评估板介绍
  • Flink安装和Flink CDC实现数据同步
  • 数字化转型助手 快鲸SCRM系统为企业营销赋能
  • 浅谈Agent
  • 绿色能源发展关键:优化风电运维体系
  • Sparrow系列拓展篇:对调度层进行抽象并引入IPC机制信号量
  • 天塌了!!!SQL竟也可以做预测分析?| 商品零售额的预测
  • VSCode本地C/C++环境配置
  • 【智能算法应用】淘金优化算法求解二维路径规划问题
  • Linux挖矿病毒(kswapd0进程使cpu爆满)
  • 【java】ArrayList与LinkedList的区别
  • 【LangChain系列6】【Agent模块详解】
  • JavaScript Cookie 与 服务器生成的 Cookie 的区别与应用
  • 深入了解Git、GitHub、GitLab及其应用技巧
  • ctfshow(316,317,318)--XSS漏洞--反射性XSS
  • Visual Studio2022版本的下载与安装
  • nodeJS程序如何引入依赖包
  • 建网站怎么建?只需几个步骤
  • 机器学习课程总结(个人向)
  • 数据分析-43-时间序列预测之深度学习方法GRU
  • Pandas | 数据分析时将特定列转换为数字类型 float64 或 int64的方法
  • Elasticsearch的自定义查询方法到底是啥?
  • Jenkins找不到maven构建项目
  • 怎么更换IP地址 改变IP归属地的三种方法
  • C#-异步查询示例
  • 设计模式之适配器模式(从多个MQ消息体中,抽取指定字段值场景)
  • vue+exceljs前端下载、导出xlsx文件
  • 算法定制LiteAIServer摄像机实时接入分析平台烟火检测算法的主要功能
  • 用 Python 从零开始创建神经网络(二)
  • 嘉吉连续第七年亮相进博会