二分演算法

⑴ 什麼是演算法上的「二分圖」概念 請簡要描述.

這個你可以去網路上看看.這算一種數據結構,不算演算法.二分圖匹配還算是一種演算法.
http://ke..com/view/501081.htm

⑵ 實現二分搜索演算法,並分析其時間復雜度

對於這樣一個謂詞f()，滿足性質：若f(a)=true，則對於任意定義域內的b>a，f(b)=true.
l與r為值域
int work ( int begin , int end ) {
while ( end - begin != 1 ) {
const int middle = ( begin + end ) / 2 ;
if ( f ( middle ) ) end = middle ;
else begin = middle ;
}
return begin ;
}
返回的是最大的x使f(x)為否

⑶ 二分搜索演算法的實現

二分搜索的時候，是要慢慢縮小搜索范圍的。比如一共有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變數傳到函數里。

⑷ 二分查找演算法

前提要求數據排好序，有遞歸和非遞歸版本
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;
}

⑸ 二分搜索演算法是利用什麼實現的演算法

二分搜索演算法是分治法裡面的一個特例，叫做減治法

⑹ 二分演算法的一些細節問題

意義就是精度
可以，隨便，越小精度越大，需要最終達到的|a-b|越小

⑺ 二分二至的計算方法

由於節氣是根據太陽在黃道上的位置而定的，因此節氣與公歷一樣是一種陽歷。故每年的節氣基本與公歷日期相對應：
上半年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日左右，這就是冬至日。

⑻ 二分查找法的具體演算法

折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用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)。在數據量很大的時候，它的線性查找在時間復雜度上的優劣一目瞭然。

⑼ 基礎二分演算法 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;
}