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--
实现代码:
网友评论