011/Algorithms
/02.查找与排序/08.二分查找/08.01.二分查找.py
# 二分查找算法
1. 二分查找算法的实现
1.1 二分查找算法的原理
1. 首先，设定数组的左右端点分别为 `l` 和 `r`，其中 `l` 为数组的起始位置，`r` 为数组的末尾位置；
2. 然后，计算 `m` 为数组的中间位置，即 `m = (r + l) // 2`；
3. 如果查找的值 `target` 等于 `arr[m]`，则表示找到了目标值，直接返回 `m`；
4. 否则，如果 `target` 小于 `arr[m]`，则说明目标值在数组的左半部分，因此更新 `r` 为 `m-1`；
5. 否则，如果 `target` 大于 `arr[m]`，则说明目标值在数组的右半部分，因此更新 `l` 为 `m+1`；
6. 重复步骤 3 到 5，直到找到目标值或 `l` 大于 `r`，即数组没有目标值，此时返回 `None`。
1.2 二分查找算法的实现
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 定义二分查找算法
l, r = 0, len(nums) - 1
while l <= r:
m = (l + r) // 2 # 计算中间位置
if nums[m] == target:
return m # 找到目标��，返回其下标
elif nums[m] < target:
l = m + 1 # 目标值在右半部分，更新左边界
elif nums[m] > target:
r = m - 1 # 目标值在左半部分，更新右边界
return -1 # 没有找到目标值，返回-1
```
2. 二分查找算法的复杂度分析
2.1 时间复杂度
二分查找算法的时间复杂度为 O(log n)，其中 n 是数组的长度。这是因为每次迭代中，数组的大小都会减少一半，即每次迭代都会减少数组的大小。因此，二分查找的时间复杂度为 O(log n)。
2.2 空间复杂度
二分查找算法的空间复杂度为 O(1)，因为算法只需要常数级的额外空间来存储变量，而不依赖于输入数组的大小。
3. 二分查找算法的应用
二分查找算法适用于有序数组的查找，可以在 O(log n) 时间复杂度内完成查找操作。此外，二分查找算法还可以用于解决一些其他问题，如查找两个有序数组的中位数等。
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
m = (l + r) // 2
if nums[m] == target:
return m
elif nums[m] < target:
l = m + 1
else:
r = m - 1
return -1
```
/02.查找与排序/02.01.查找.py
# 02.查找与排序
2.01.查找
2.1 哈希表查找
哈希表查找是通过将数组元素存储到哈希表中，然后通过哈希表的查找操作来快速查找目标值。哈希表查找的时间复杂度为 O(1)，空间复杂度为 O(n)。
2.2 二分查找
二分查找是通过将数组元素排序后，使用二分查找算法来快速查找目标值。二分查找的时间复杂度为 O(log n)，空间复杂度为 O(1)。
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 定义哈希表查找算法
hash_map = {}
for num in nums:
hash_map[num] = True
if target in hash_map:
return hash_map[target]
else:
return -1
```
```python
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 定义二分查找算法
l, r = 0, len(nums) - 1
while l <= r:
m = (l + r) // 2
if nums[m] == target:
return m
elif nums[m] < target:
l = m + 1
else:
r = m - 1
return -1
```
2.3 查找最大最小值
查找最大最小值可以通过遍历数组元素，然后比较每个元素的大小来实现。查找最大值的时间复杂度为 O(n)，查找最小值的时间复杂度也为 O(n)。
```python
class Solution:
def findMax(self, nums: List[int]) -> int:
# 查找最大值
max_num = nums[0]
for num in nums: