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

释放双眼,带上耳机,听听看~!

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  题解

528. Random Pick with Weight 
题解

 

按值范围折半查找

折半查找还可以应用于非有序区间查找满足特定条件的值。该场景下所找的值
在已知范围内,这时折半的不是索引,而是
值本身所在的范围。算法基本框架如下:

    //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题:

287. Find the Duplicate Number 
题解

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 的位置,最终最长的序列长度即为所求。详细算法过程说明见 这里

相关LeetCode题:

300. Longest Increasing Subsequence  题解

354. Russian Doll Envelopes 
题解

人已赞赏
随笔日记

在Winform系统界面中对进展阶段的动态展示和处理

2020-11-9 4:20:44

随笔日记

Java学习点滴——初识Java

2020-11-9 4:20:46

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索