二分查找

描述

二分查找是一种算法，其输入是一个有序的元素列表（元素可比较），如果查找的元素包含在列表中，二分查找返回其位置，否则返回NULL

具体步骤

1. 设置指针
   • l= 数组起点
   • r= 数组终点
   • m= (l+r)/2
2. g = 目标值
3. • 如果 g>[m] : l = m+1
   • 如果 g<[m] : r = m-1
   • 如果 g=[m] : 找到g在数组中的位置 m
4. 如果 r<[l]: 数组中找不到 g,返回空值
   返回第3部继续执行

变形问题

有序数组旋转 [0,1,2,4,5,6,7] -> [2,4,5,6,7,0,1,] 后进行查找(思路仍然是二分查找)，要求时间复杂度是O(logN)

解决方法：

1.找到数组中最小的点，并拆分成2个问题，用二分查找

具体步骤

1. 设置指针
   • l= 数组起点
   • r= 数组终点
   • m= (l+r)/2
2. • 如果 [m]<[l] ：r = m
   • 如果 [m]>[l] : l = m
3. • 如果 r-l<=1：
     • 如果 l<r : l是数组中最小点的位置，将l作为最小点 min记录，并跳到第四步
     • 否则 r 是数组中最小点的位置，将r作为最小点 min记录，并跳到第四步
   • 回到第二步
4. 初始化查找
   • l = 数组起点
   • r = min
   • m = (1+r)/2
5. 用普通的二分查找进行搜索，如果搜索到结果，则返回这个结果
6. 初始化查找
   • l = min
   • r = 数组终点
   • m = (1+r)/2
7. 回到第5步

2. 直接搜索

具体步骤

1. 设置指针
   • l = 数组起点
   • r = 数组终点
   • m = (l+r)/2
   • g = 目标值
2. • 如果 [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