数组基础 二分查找

今日任务1. 吃透 LeetCode 704. 二分查找2. 熟练写出 左闭右闭 [left, right] 和 左闭右开 [left, right) 两种版本3. 了解数组基础特性 内存空间布局题目信息• 题目 二分查找• 链接https://leetcode.cn/problems/binary-search/• 视频讲解https://www.bilibili.com/video/BiA4y1o715一、数组基础要点• 数组在内存中是连续存储空间• 下标从 0 开始• 支持随机访问访问元素 O(1)• 插入/删除元素需要移动数据效率较低二、二分查找两种标准写法1左闭右闭[left, right]最常用def search(nums, target):left 0right len(nums) - 1while left right:mid left (right - left) // 2if nums[mid] target:return midelif nums[mid] target:left mid 1else:right mid - 1return -1规则•初始right len(nums)-1•循环left right•收缩left mid1 / right mid-12左闭右开[left, right)def search(nums, target):left 0right len(nums)while left right:mid left (right - left) // 2if nums[mid] target:return midelif nums[mid] target:left mid 1else:right midreturn -1规则• 初始right len(nums)• 循环left right• 收缩left mid1 / right mid解答: