Binary Search基础
应用于已排序的数据查找其中特定值,是折半查找最常的应用场景。相比线性查找(Linear Search),其时间复杂度减少到O(lgn)。算法基本框架如下:
//704. Binary Search int search(vector<int>& nums, int target) { //nums为已排序数组 ,j=nums.size()-; while(i<=j){ ; if(nums[mid]==target) return mid; ; ; } ; }
以上查找范围的上下限 i 和 j 代表索引,算法过程可视化:Binary Search,STL中有序区间函数upper_bound/lower_bound内用的查找方法即是折半查找。
相关LeetCode题:
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(); ,j=n-; //[i,j]表示值的区间 while(i<=j){ ,count=; for(auto k:nums) ; ; } return i; //最终返回值本身 }
相关LeetCode题:
378. Kth Smallest Element in a Sorted Matrix 题解
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) { ; vector<int> tail(nums.size()); //候选递增序列集for(auto num:nums){ ,j=size; while(i<j){ ; ; else j=mid; } tail[i]=num; if(i==size) size++; } return size; }
以上设定LIS候选序列集 tail,对无序区间 nums 中的各个值通过折半查找的方法,找到其落在 tail 的位置,最终最长的序列长度即为所求。详细算法过程说明见 这里 这里