数组基础 二分查找

今日任务

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 = 0
right = len(nums) - 1

while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
规则

•初始：right = len(nums)-1

•循环：left <= right

•收缩：left = mid+1 / right = mid-1
2）左闭右开[left, right)
def search(nums, target):
left = 0
right = len(nums)

while left < right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid
return -1
规则

• 初始：right = len(nums)

• 循环：left < right

• 收缩：left = mid+1 / right = mid

解答: