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 https://leetcode.com/problems/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 https://leetcode.com/problems/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 题解
来源: https://www.cnblogs.com/bangerlee/p/10693593.html