Template Series - Dichotomous

二分模板

1、Binary search on integers

Binary search on integers,Because when narrowing your search,有可能 $r=mid-1$或 $l=mid+1$,因此可以用 $ans$ 记录可行解.Does it need to be reduced 1 或加 1 ,Analyze on a case-by-case basis.

l=a;
r=b; //Initial search range
while(l<=r) {
    
	int mid=(l+r)/2;
	if(judge(mid)) {
    
		ans=mid; //记录可行解
		r=mid-1;
	}
	else
		l=mid+1;
}

2、Binary search on real numbers

Binary search on real numbers cannot directly compare magnitudes,可以采用 $r-l>eps$ 作为循环条件,$eps$ to a smaller number,如 $1e-7$ 等.To avoid losing possible solutions,缩小范围时 $r=mid$ 或 $l=mid$ ,Returns the last feasible solution at the end of the loop.

l=a; r=b; //Initial search range
while(r-l>eps){
    //判断差值
    double mid=(l+r)/2;
    if(judge(mid))
        l=mid;  //lFeasible solutions are recorded,Returns the answer after the loop endsl
    else
        r=mid;
}
// l 是答案

It is also possible to run a fixed number of times,如运行100次,可达 $10^{-30}$ 精度,In general, the problem can be solved.

l=a;
r=b;
for(int i=0; i<100; i++) {
     //运行100次
	double mid=(l+r)/2;
	if(judge(mid))
		l=mid;
	else
		r=mid;
}
// l 是答案

3、二分搜索详解

例如,给定n个元素序列,这些元素是有序的（假定为升序）,从序列中查找元素x.

用一维数组S[]存储该有序序列,设变量low和high表示查找范围的下界和上界,middle表示查找范围的中间位置,x为特定的查找元素.

3.1 算法步骤

（1）初始化.令low=0,即指向有序数组S[]的第一个元素;high=n−1,即指向有序数组S[]的最后一个元素.

（2）判定low≤high是否成立,如果成立,转向第3步,否则,算法结束.

（3）middle=(low+high)/2,即指向查找范围的中间元素.如果数量较大,为避免low+high溢出,可以采用middle=low+(high-low)/2.

（4）判断x与S[middle]的关系.如果x=S[middle],则搜索成功,算法结束;如果x>S[middle],则令low=middle+1;否则令high=middle−1,转向第2步.

3.2 算法实现

用 BinarySearch(int n, int s[], int x)The function implements the halved search algorithm,其中 $n$ 为元素个数,$s[]$ 为有序数组,$x$ 为待查找元素.$low$ 指向数组的第一个元素,$high$ 指向数组的最后一个元素.如果 $low\le high$,$middle=(low+high)/2$,即指向查找范围的中间元素.如果$x=S[middle]$ ,搜索成功,算法结束;如果 $x>S[middle]$,则令 $low=middle+1$ ,Go to the second half of the search;否则令 $high=middle-1$ ,Go to the first half of the search.

3.2.1 非递归算法

int BinarySearch(int s[],int n,int x) {
     //二分查找非递归算法
	int low=0,high=n-1;  //low指向数组的第一个元素,high指向数组的最后一个元素
	while(low<=high) {
    
		int middle=(low+high)/2;  //middle为Find the middle value of the range
		if(x==s[middle])  //x等于Find the middle value of the range,算法结束
			return middle;
		else if(x>s[middle]) //x大于查找范围的中间元素,则从左半部分查找
			low=middle+1;
		else            //x小于查找范围的中间元素,则从右半部分查找
			high=middle-1;
	}
	return -1;
}

3.2.2 递归算法

Recursion has self-invocation problem,增加两个参数 low 和 highto mark the start and end of the search range.

int recursionBS(int s[],int x,int low,int high) {
     //二分查找递归算法
	//lowPoints to the first element of the search range,highPoints to the last element of the search range
	if(low>high)              //递归结束条件
		return -1;
	int middle=(low+high)/2; //计算middle值(Find the middle value of the range)
	if(x==s[middle])        //x等于s[middle],查找成功,算法结束
		return middle;
	else if(x<s[middle]) //x小于s[middle],Search from the first half
		return recursionBS(s,x,low,middle-1);
	else            //x大于s[middle],Search from the second half
		return recursionBS(s,x,middle+1,high);
}

3.2.3 算法分析

3.2.3.1 时间复杂度

二分查找算法,How to calculate time complexity？如果用T(n)来表示nThe time complexity of the binary search algorithm for an ordered element,那么：

• 当n=1时,A comparison is required,T(n)=O(1).
• 当n>1时,The element to be found is compared with the element at the middle position,需要O(1)时间,如果比较不成功,Then you need to search in the first half or the second half,问题的规模缩小了一半,时间复杂度变为 $T(\frac{n}{2})$ .

The non-recursive algorithm of binary search is the same as the recursive algorithm,时间复杂度相同,均为 $O(logn)$.

3.2.3.2 空间复杂度

in a non-recursive binary search algorithm,Variables take up some auxiliary space,这些辅助空间都是常数阶的,因此空间复杂度为 $O(1)$.

二分查找的递归算法,Except using some variables,Recursive calls also need to use the stack to achieve.在递归算法中,Each recursive call requires a stack space storage,Then we just need to see how many calls there are.假设原问题的规模为n,Then the first recursion is divided into two scales $\frac{n}{2}$ 的子问题,Not each of these two subproblems is executed,Only one of them will be executed.Because after comparing with the median value,Or go to the first half to find out,Or go to the second half to find;Then set the scale to $\frac{n}{2}$ The subproblems continue to be divided into two scales as $\frac{n}{4}$ 的子问题,选择其一;继续分治下去,In the worst case, divide and conquer until only one value remains,Then the number of nodes that the algorithm executes is the nodes passed from the root to the leaf,Execute one for each layer,直到最后一层,如图所示.

The final size of the recursive call is 1,即 $\frac{n}{2x}=1$,则 $x=logn$ .It is assumed that the shaded part is the path traversed by the search,一共经过了 $logn$ 个节点,That is to say, it is called recursively $logn$ 次.The stack space used by the recursive algorithm is the depth of the recursion tree,Therefore, the space complexity of the recursive binary search algorithm is $O(logn)$ .

4、There are several issues that need to be paid attention to in binary search

1. Ordering must be satisfied.
2. 搜索范围.初始时,A search scope needs to be specified,如果不知道具体范围,Positive numbers can take a range $[0,inf]$ ,It is possible for negative numbers to take a range[-inf,inf],inf为无穷大,通常设定为 $0x3f3f3f3f$.
3. 二分搜索.一般情况下,$mid=(l+r)/2$ 或 $mid=(l+r)>>1$ .如果l和r特别大,为避免 $l+r$ 溢出,可以采用 $mid=l+(r-l)/2$ .Determines the conditions for ending the binary search,and when judged $mid$ Search for the first half when feasible,Or to the second half of the search,需要具体问题具体分析.
4. 答案是什么.Be especially careful when the search range is reduced,Is it lostmid点上的答案.