二分查找算法上篇

一. 二分查找二分查找

1.题目

2. 算法原理

解法一：暴力求解

一般而言，当我们拿到此题的时候，映入脑海的第一想法无非就是暴力求解。

对于此题，直接一个for循环，即可完成此题

时间复杂度：O(N)

解法二：二分查找

1）先定义2个指针

left = 0,right = n-1; 注意这里的 n  代表当前数组的大小

2）mid = left +( right - left ) / 2

3) 循环结束条件： left <= right

3. 分析

时间复杂度：long N

4.OJ 代码

1)暴力求解代码

2）二分查找代码

二·x 的平方根

1.题目

2. 算法原理

1)暴力求解：

从1遍历到x 一次判断当前的平方是否满足要求

2）二分查找算法：

对1~x 某一个数进行求平方一定存在某一个数是小于或者是等于x 

根据这一特性可以把数组进行二段性的划分：

一部分数据是 <=  x

一部分数据是 > x

3. 分析

时间复杂度：log N

1)  指针的初始位置 ：

left = 1，right = x

2）循环结条件：

left  < right

注意这里不能是 left <= right 

当left == right 的时候，若是进入循环，此时导致left ,right ,mid 三者指向同一个位置，mid  会永远

指向当前位置，导致进入死循环。

3）迭代部分：

当 mid * mid  <= x :  left = mid, 这里依然是不能让 left = mid+1

当此时只剩下2个数据恰好mid  是指向第一个数据的，并且 mid* mid < x ，若是left = mid+1 此时

会恰好错过

当 mid * mid > x:   right = mid-1

 4）细节处理

对mid 指向的数据进行平方的时候，可能存在数据溢出，所以此时mid 的数据类型应该是 

long  long

4.OJ 代码

三·搜索插入位置

1.题目

2. 算法原理

1）暴力求解：

进行一次遍历

 对于  target  这个数值无非有两种情况：

一个是 小于数组最后 一个 元素；另一种是大于数组的最后一个元素

2）二分查找

3. 分析

二分查找时间复杂度： log N 

首先已知数组是有序的，利用这一特性进行二段性的划分即可

1）初始位置

left = 0,right = n-1;

2) 迭代部分：

if ( nums[mid] > target )  right = mid -1;

if(nums[mid] <= target)   left = mid;

3) 判断部分：

left < right

4）细节处理：

 

 当left 与right 相遇的时候，此时nums[left] 与target 存在2钟情况，当 nums[left] <=target 的时候，

即使target 不存在数组里面，要进行插入，当前位置就是；

当nums[left] > target  的时候，说明当前数据不存在数组

4.OJ 代码

1)暴力代码：

2）二分查找：

 四·寻找峰值

1.题目

2.算法原理

1.暴力求解

对数组进行一次遍历，找出一个元素要求大于后面的元素，同时大于前面的元素

时间复杂度：O(N )

2.二分查找

利用题目已经给出的条件：峰值是指大于左右相邻的元素的

所以利用这一特性可以进行二段性的划分

时间复杂度：log N

3.分析

题目说明了：数组的大小至少的大于1的，也就是说，一定是存在峰值的。只有有一个峰值还是多

个峰值无所谓的。

1）初始位置：

left = 0, right = n-1 (n :数组大小)

mid = left +(right - left )/2

2)判断部分：

left < right

3）迭代部分

当 nums[mid] > nums[mid-1] :  left = mid

否则 ：right = mid-1

4.代码

1）暴力求解

2）二分查找