• <sup id="mk476"></sup>
    <dl id="mk476"></dl>
  • <progress id="mk476"><tr id="mk476"></tr></progress>
    <div id="mk476"><tr id="mk476"></tr></div>
    <sup id="mk476"><ins id="mk476"></ins></sup>
  • <progress id="mk476"></progress>
    <div id="mk476"></div>
    <div id="mk476"><tr id="mk476"></tr></div>
  • <div id="mk476"></div>
    <dl id="mk476"><s id="mk476"></s></dl><dl id="mk476"></dl><div id="mk476"></div>
  • <div id="mk476"></div>
    <dl id="mk476"><ins id="mk476"></ins></dl>
    代码改变世界

    LeetCode编程训练 - 折半查找(Binary Search)

    2019-04-12 11:39 by bangerlee, ... 阅读, ... 评论, 收藏, 编辑

    Binary Search基础

    应用于已排序的数据查找其中特定值,是折半查找最常的应用场景。相比线性查找(Linear Search),其时间复杂度减少到O(lgn)。算法基本框架如下:

       //704. Binary Search
    int search(vector<int>& nums, int target) { //nums为已排序数组 int i=0,j=nums.size()-1; while(i<=j){ int mid=(i+j)/2; if(nums[mid]==target) return mid; else if(nums[mid]>target) j=mid-1; else i=mid+1; } return -1; }

    以上查找范围的上下限 i 和 j 代表索引,算法过程可视化:Binary Search,STL中有序区间函数upper_bound/lower_bound内用的查找方法即是折半查找。

    相关LeetCode题:

    704. Binary Search  题解

    34. Find First and Last Position of Element in Sorted Array  题解

    33. Search in Rotated Sorted Array  题解

     

    按值范围折半查找

    折半查找还可以应用于非有序区间查找满足特定条件的值。该场景下所找的值在已知范围内,这时折半的不是索引,而是值本身所在的范围。算法基本框架如下:
        //287. Find the Duplicate Number
    int
    findDuplicate(vector<int>& nums) { int n=nums.size(); int i=1,j=n-1; //[i,j]表示值的区间 while(i<=j){ int mid=(i+j)/2,count=0; for(auto k:nums) if(k<=mid) ++count; //根据计数折半缩小区间if(count<=mid) i=mid+1; else j=mid-1; } return i; //最终返回值本身 }

    相关LeetCode题:

    378. Kth Smallest Element in a Sorted Matrix  题解 

    875. Koko Eating Bananas  题解

    1011. Capacity To Ship Packages Within D Days  题解

    410. Split Array Largest Sum   题解

     

    折半查找求递增序列

    求递增序列(LIS, longest increasing subsequence)是一道经典的算法题目,用折半查找对其进行求解的方法十分巧妙,求解代码如下:

        //300. Longest Increasing Subsequence
    int lengthOfLIS(vector<int>& nums) { int size=0; vector<int> tail(nums.size()); //候选递增序列集for(auto num:nums){ int i=0,j=size; while(i<j){ int mid=(i+j)/2; if(tail[mid]<num) i=mid+1; else j=mid; } tail[i]=num; if(i==size) size++; } return size; }

    以上设定LIS候选序列集 tail,对无序区间 nums 中的各个值通过折半查找的方法,找到其落在 tail 的位置,最终最长的序列长度即为所求。详细算法过程说明见 这里 这里

    江苏11选5软件