美文网首页
二分查找专题

二分查找专题

作者: 少冰三hun甜 | 来源:发表于2016-10-25 09:38 被阅读51次

    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--
    实现代码:


    相关文章

      网友评论

          本文标题:二分查找专题

          本文链接:https://www.haomeiwen.com/subject/wutquttx.html