1 二分查找jdk源码 时间O(logn)空间O（1）
递归式写法： 时间和空间都是O(logn)
2. 二分插入
3.范围查找
这题的重点在于查找的细节，加入要找目标元素的左边界：
- 当nums[mid]==target的时候，那么mid的左边有可能还有target元素，所以此时可以让（右指针）hi=mid，下一次在左边查找。
- 当nums[mid]>target的时候，target肯定在左边，所以hi=mid.
- 当nums[mid]<target的时候，target肯定在右边，所以lo=mid+1;
查找右边界也同理
示例代码：
4.杨氏矩阵(上)
思路一：二分查找列再二分查找行，或者二分查找行再二分查找列。
思路二：巧妙变化直接把矩阵当做一个长数列，
5 杨氏矩阵Ⅱ
这题和上题不一样的是，完全没法先确定行再确定列。
流程示意
示例代码
6.函数的极大值
思路，去三个指针 start,mid,end,每次判断mid的所处的位置，如果是递增的很明显最大值在右边，如果是递减的最大值明显在左边，通过这种方式二分，使运行时间为logn。
实现代码：
7.寻找旋转数组的最小值。
8.寻找旋转数组的最小值Ⅱ
这题和上题不一样的地方就是可能包含重复元素，要求寻找第一个最小元素的坐标。比如【3，3，3，1，1，1，2，2，2】，返回3.
思路分析：
这次看起来貌似可以用上一题的思路来解决，由于上一题判断nums[end]和nums[mid]的大小而且不会有重复元素，所以一定能划分，。但假如有重复元素可能会出现nums[mid]==nums[end] 此时无法判断木匾元素在mid的左边还是右边，比[2，2，2，2，1，2，2] 和[2，1，2，2，2，2，2]他们的nums【mid】和nums【end】都是相同的。
此时的最小值可能是nums【mid】和nums【end】，也可能是在他们之间，但可以确定的是把end指针王往中间收缩end--，不会影响最小值的查找因为即使最小值为为nums【mid】和nums【end】，可以保证nums【mid】还在查找范围内，而且这样线性缩小了查找范围。
所以算法思路是这样：
实现代码：
9.旋转数组的查找1
题目描述：在没有重复值而且为升序的旋转数组查找特定值，如果找到就返回下标，否则返回-1；
有了上面几题的思路，很容易会想到借助二分法和三个指针解决问题。
思路：d定义三个指针lo, mid,hi不断比较端点指针hi（lo也行）和mid指向的值的大小。
1 假如nums【hi】<nums【mid】那么一定是类似下图的情况，此时lo和mid之间有序，可以判断是否在里边，如果在，那么变换hi指针的值hi=mid-1,下次循环在mid左边查找，如果不在，那么变换lo指针的值lo=mid+1,下次在mid右边查找。
2 假如nums【hi】>nums【mid】那么是类似下图的情况，此时mid和hi之间有序，可以判断是否在里边，如果在，那么变换lo指针的值lo=mid+1,下次循环在mid左边查找，如果不在，那么变换hi指针的值hi=mid-1,下次在mid右边查找
10.旋转数组的查找2
和1不同的是这题的旋转排序数组可能会有相同元素，那么多一种情况就是边界指针lo 或者hi指向的元素值有可能和mid指向的元素值相同。
比如【1111001】和【1001111】无法判断哪边的元素有序，解决芳芳跟寻找旋转数组最小值的方式一样，线性缩小查找范围lo++，或者hi--
实现代码：
网友评论