二分查找
描述
二分查找是一种算法，其输入是一个有序的元素列表（元素可比较），如果查找的元素包含在列表中，二分查找返回其位置，否则返回NULL
具体步骤
- 设置指针
- l= 数组起点
- r= 数组终点
- m= (l+r)/2
- g = 目标值
- 如果 g>[m] : l = m+1
- 如果 g<[m] : r = m-1
- 如果 g=[m] : 找到g在数组中的位置 m
- 如果 r<[l]: 数组中找不到 g,返回空值
返回第3部继续执行
变形问题
有序数组旋转 [0,1,2,4,5,6,7] -> [2,4,5,6,7,0,1,] 后进行查找(思路仍然是二分查找)，要求时间复杂度是O(logN)
解决方法：
1.找到数组中最小的点，并拆分成2个问题，用二分查找
具体步骤
- 设置指针
- l= 数组起点
- r= 数组终点
- m= (l+r)/2
- 如果 [m]<[l] ：r = m
- 如果 [m]>[l] : l = m
- 如果 r-l<=1：
- 如果 l<r : l是数组中最小点的位置，将l作为最小点 min记录，并跳到第四步
- 否则 r 是数组中最小点的位置，将r作为最小点 min记录，并跳到第四步
- 回到第二步
- 如果 r-l<=1：
- 初始化查找
- l = 数组起点
- r = min
- m = (1+r)/2
- 用普通的二分查找进行搜索，如果搜索到结果，则返回这个结果
- 初始化查找
- l = min
- r = 数组终点
- m = (1+r)/2
- 回到第5步
2. 直接搜索
具体步骤
- 设置指针
- l = 数组起点
- r = 数组终点
- m = (l+r)/2
- g = 目标值
- 如果 [m]<[l]: 说明右边是有序的
- g > [m] 且 g<[r] : l = m+1
- g = [m] : 位置m 是目标g的位置，并返回
- 前面的都不满足： r = m - 1
- 如果 [m]>[l]: 说明左边是有序的
- g<[m] 且 g>[l] : r = m-1
- g = [m] : 位置m 是目标g的位置，并返回
- 前面的都不满足： l = m - 1
- 如果 [m]<[l]: 说明右边是有序的
