二分算法

‘壹’ 二分排序法的算法思想是什么如何进行二分排序...不是插入和查找

个人认为和快排的思路是一样的。。。数组当中随机找一个支点(pivot)，小于它的所有数放一边a1，大于它的所有数放另一边b1。然后，在a1，b1中使用相同的思路进行排序，也就是递归啦。

直到递归到基础情况（即一个数组中只有2-5个数的时候）。使用最基本的排序算法进行排序。

‘贰’ 二分算法的一些细节问题

意义就是精度
可以，随便，越小精度越大，需要最终达到的|a-b|越小

‘叁’ 基础二分算法 C++

#include<stdio.h>
int	main(void)
{
	int	min,max,m;
	int	num,cnt;
	printf("输入0到10000的数值");
	scanf("%d",&num);
	min=0;max=10000;cnt=1;
	for(m=(min+max)/2;min<=max;cnt++)
	{
		if(num>m){min=m;m=(min+max)/2;continue;}
		if(num==m)
		{
			printf("%d在第%d次找到。
",num,cnt);
			return0;
		}
		if(num<m){max=m;m=(min+max)/2;continue;}
	}
	printf("%d次查找%d没有找到
",cnt,num);
	return0;
}

‘肆’ 二分二至的计算方法

由于节气是根据太阳在黄道上的位置而定的，因此节气与公历一样是一种阳历。故每年的节气基本与公历日期相对应：
上半年6、21，下半年9、23，
最多相差一、两天。
二分二至其实就是春分、秋分、夏至和冬至的合称，南北半球的这四个点日期不一致，但可以这样来认识：
如果在北半球，
3月19日，或20日，或21日，春分----当太阳直射在赤道并开始向北回归线移动时，就是每年的3月20日，是为中国农历的春分；
6月21日或22日，夏至----当太阳直射北回归线并开始向赤道回归时，就是每年6月21日，是为中国农历的夏至日，这一天北半球进入盛夏；
9月22日或23日，秋分----当太阳从北回归线回归，直射赤道，并向南回归线移动时，就是每年的9月23日，是为中国农历的秋分，北半球因为太阳照射时间变短，照射角度越来越大，逐渐转凉；
12月21日，或22日，或23日，冬至----当太阳到达其最南端的直射点——南回归线时，就是每年的12月22日左右，是为中国农历的冬至，这一天是北半球日照最短的一天，天气变得寒冷。
在南半球刚好相反！
二分二至产生的根本原因是由于地球在自转的同时绕太阳公转，使太阳直射点在南北回归线之间做回归运动所致。
由于地球自转和公转不在同一个水平面内，当地球绕日公转时，随着时间的推移，太阳直射点在地球上的位置也在不断的变化：
每年的3月21日左右，当太阳直射点刚好直射在赤道上时，全球所有地区在一年中第一次昼夜等长，南北半球也第一次受到相等的太阳辐射，这一天是春分日；
地球继续绕日公转，到每年的6月22日左右，太阳直射到地球上的直射点达到一年中所能达到的最北端，即23°26′N。此时北半球是一年中太阳辐射最多的一天，相应的南半球所受太阳辐射是一年中最少的时候，这一天就是夏至日；
在达到最北直射点后，太阳直射向南运动，当再一次直射赤道时，全球所有地区在一年中第二次昼夜等长，南北半球在一年中第二次受到相同的太阳辐射，这种情况出现在每年的9月23日左右，是为秋分日；
太阳直射点继续向南运动，当到达其所能到达的最南端时，南半球是一年中太阳辐射最多的一天，相应的北半球所受太阳辐射是一年中最少的时候，此时太阳直射纬度是23°26′S，日期是每年的12月22日左右，这就是冬至日。

‘伍’ 二分搜索算法是利用什么实现的算法

根据分治策略来实现

‘陆’ 二分查找算法

前提要求数据排好序，有递归和非递归版本
int binSearch(const int *Array,int start,int end,int key)
{
int left,right;
int mid;
left=start;
right=end;
while (left<=right) { /注释中为递归算法，执行效率低，不推荐
mid=(left+right)/2;
/* if (key<Array[mid]) {
return(binSearch(Array,left,mid,key));
}
else if(key>Array[mid]){
return (binSearch(Array,mid+1,right,key));
}
else
return mid;
*/
if (key<Array[mid]) {
right=mid-1;
}
else if(key>Array[mid]){
left=mid+1;
}
else
return mid;
}
return -1;
}

‘柒’ 二分搜索算法的实现

二分搜索的时候，是要慢慢缩小搜索范围的。比如一共有10个，那么middle是5,下一层搜索的范围应该是1-4和6-10。你的函数里没有这个功能。搜索函数至少应该是int BinarySearch(Type a[], const Type& x,int left, int right);终止条件就是if(left > right) 你定义y的时候是在main函数里，所以BinarySearch里面不能直接用y，解决方式是在外部定义一个全局的y变量，或者把y变量传到函数里。

‘捌’ 二分查找法的具体算法

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解，但是要写一个正确的二分搜索算法也不是一件简单的事。第一个二分搜索算法早在1946年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的着作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的，我们可用C++描述如下：

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函数BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n个升序排列的元素中搜索x,找到x时返回其在数组中的位置，否则返回-1。容易看出，每执行一次while循环，待搜索数组的大小减少一半,因此整个算法在最坏情况下的时间复杂度为O(log n)。在数据量很大的时候，它的线性查找在时间复杂度上的优劣一目了然。

‘玖’ 二分算法使用

#include<bits/stdc++.h>
using namespace std;
int a[1000009];
inline int read(){
int res=0,k=1;char s;
while(!isdigit(s=getchar())) if(s=='-') k=-1;
while(isdigit(s)) res=res*10+s-'0',s=getchar();
return res*k;
}
int cha(int i,int n,int nm){
if(i==n){
//cout<<i<<endl;
if(a[i]==nm) return i;
else return -1;
}
int mid=(i+n)/2;//cout<<a[mid]<<endl;
if(a[mid]<nm) cha(mid+1,n,nm);
else cha(i,mid,nm);
}
int main(){
int n,m,nm;n=read(),m=read();
for(int i=0;i<n;i++) a[i]=read();
for(int i=0;i<m;i++){
nm=read();int k=cha(0,n-1,nm);
if(k==-1) cout<<-1<<' '<<-1<<endl;
else{
cout<<k<<' ';
for(k=k;;k++) if(a[k]!=nm) break;
cout<<k-1<<endl;
}
}
return 0;
}