Binary Search基础
应用于已排序的数据查找其中特定值，是折半查找最常的应用场景。相比线性查找(Linear Search)，其时间复杂度减少到O(lgn)。算法基本框架如下：
//704. Binary Search
int search(vector<int>& nums, int target) { //nums为已排序数组
int i=,j=nums.size()-;
while(i<=j){
int mid=(i+j)/;
if(nums[mid]==target) return mid;
else if(nums[mid]>target) j=mid-;
else i=mid+;
}
return -;
}
以上查找范围的上下限 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();
int i=,j=n-; //[i,j]表示值的区间
while(i<=j){
int mid=(i+j)/,count=;
for(auto k:nums)
if(k<=mid) ++count; //根据计数折半缩小区间if(count<=mid) i=mid+;
else j=mid-;
}
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) {
int size=;
vector<int> tail(nums.size()); //候选递增序列集for(auto num:nums){
int i=,j=size;
while(i<j){
int mid=(i+j)/;
if(tail[mid]<num) i=mid+;
else j=mid;
}
tail[i]=num;
if(i==size) size++;
}
return size;
}
以上设定LIS候选序列集 tail，对无序区间 nums 中的各个值通过折半查找的方法，找到其落在 tail 的位置，最终最长的序列长度即为所求。详细算法过程说明见 这里 这里