# 二分查找及对应经典题目-问答-阿里云开发者社区-阿里云

## 二分查找及对应经典题目

2020-07-03 16:20:06 622 1

``````def BinarySearch(nums,target):
left,right = 0,len(nums)-1
while left<=right:
mid = left+(right-left)//2 #计算数组中间位置
if nums[mid] == target:
return mid #找到并返回
# 中间元素大于目标值，搜索数组左半部分
elif nums[mid] > target:
right = mid - 1
# 中间元素小于目标值，搜索数组右半部分
elif nums[mid] < target:
left = mid + 1
return -1 #没找到目标值
``````

1、搜索旋转排序数组

• 你可以假设数组中不存在重复的元素。

• 你的算法时间复杂度必须是 O(log n) 级别。

``````def search(nums, target):
if not nums:  # 空数组
return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]:  #左半部分有序
# 先判断目标值是否存在有序的半个数组中
if nums[0] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
elif nums[0] > nums[mid]: #右半部分有序
if nums[mid] < target <= nums[-1]:
left = mid + 1
else:
right = mid - 1
return -1

``````

2、在排序数组中查找元素的第一个和最后一个位置

``````def searchRange(nums,target):
res = [-1,-1]
if not nums: #空数组
return res
def leftbound(nums,target): #找到左侧边界
left,right = 0,len(nums)-1
while left<=right:
mid = left + (right-left)//2
if nums[mid]>target:
right = mid-1
elif nums[mid]<target:
left = mid+1
elif nums[mid] == target:
right = mid-1 #不返回，收缩右侧边界
#判断是否越界
if(left>=len(nums) or nums[left]!=target):
return -1
return left
def rightbount(nums,target): # 找到右侧边界
left,right = 0,len(nums)-1
while left<=right:
mid = left + (right-left)//2
if nums[mid]>target:
right = mid-1
elif nums[mid]<target:
left = mid+1
elif nums[mid] == target:#不返回，收缩左侧边界
left = mid+1
#判断是否越界
if(right<0 or nums[right]!=target):
return -1
return right
res[0] = leftbound(nums,target)
res[1] = rightbount(nums,target)
return res
``````

3、搜索二维矩阵

``````def searchMatrix(matrix,target):
m = len(matrix)#行
if m == 0:
return False
n = len(matrix[0])#列
left,right = 0,m*n-1
while left<=right:
mid = left + (right-left)//2
row = mid // n #元素在矩阵中的行
col = mid % n #元素在矩阵中的列
if matrix[row][col] == target:
return True
else:
if matrix[row][col]>target:
right = mid - 1
else:
left = mid + 1
return False
``````

10

【精品问答合集】Hbase热门问答

hbase小能手 2019-05-29 14:37:26 120887浏览量 回答数 10

38

xiaofanqie 2014-12-25 15:13:38 92130浏览量 回答数 38

8

OceanBase 使用动画（持续更新）

mq4096 2019-02-20 17:16:36 337130浏览量 回答数 8

111

OSS存储服务-客户端工具

newegg11 2012-05-17 15:37:18 295716浏览量 回答数 111

23

【云服务器分享】网站访问速度快才是硬道理

dreamdoo 2012-10-15 10:15:02 85405浏览量 回答数 23

62

27

qilu 2014-01-06 18:14:06 96154浏览量 回答数 27

23

【精品问答合集】Redis热门问答

2

fanyue88888 2012-12-07 15:54:30 204444浏览量 回答数 2

11

【精品问答合集】MongoDB热门问答

+关注
3

4679

《2021云上架构与运维峰会演讲合集》

《零基础CSS入门教程》

《零基础HTML入门教程》