二分查找遞歸演算法scala

⑴ 二分查找演算法

二分查找演算法，該演算法要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。如果一個序列是無序的或者是鏈表，那麼該序列就不能使用二分查找。

二分查找演算法原理：若待查序列為空，則返回-1，並退出演算法；若待查序列不為空，則將它的中間元素與目標數值進行比較，判斷是否相等；若相等，則返回中間元素索引，並退出演算法；此時已查找成功。若不相等，則比較中間元素與目標數值的大小。

二分查找的一個技巧是：不要出現else，而是把所有情況用else，if寫清楚，這樣可以清楚地展現所有細節。本文都會使用else，if，旨在講清楚，讀者理解後可自行簡化。

⑵ 用遞歸實現二分查找，有20個從小到大排好的數據，輸入b，判斷他是否在數組中

你源代碼中

mid = (x+y)/2；這句沒有問題，但是考慮一下如下情況

x = 1 y =2的時候，這時候mid會是1，如果找不到，繼續find時x y依舊是1 和2 ，程序死循環了。

修改了一下代碼

#include<iostream>
usingnamespacestd;
boolc=false;
inta[100];
intb;
voidfind(int,int);
intmain()
{
for(inti=0;i<20;++i)
	cin>>a[i];
cin>>b;
find(0,19);
if(c==true)
	cout<<"yes";
elsecout<<"no";

cin>>b;
return0;
}
voidfind(intx,inty)
{
	intmid=(x+y)/2;
	if(a[mid]==b)
	{
		c=true;
		return;
	}
	elseif(x>y)
		return;
	else
	{
		if(a[mid]<b)find(mid+1,y);
		if(a[mid]>b)find(x,mid-1);
	}
}

⑶ 數據結構的一點小問題 誰能幫我回答下啊

1.向單鏈表的末尾添加一個元素的演算法
Void InsertRear(LNode*& HL,const ElemType& item)

{
LNode*newptr;
newptr=new LNode;
If(_­­­­_newptr==NULL_____) //判斷分配的新節點是否成功
{
Printf("Menory allocation failare!");
exit(1);
}

_newptr__=item; //在新節點保存數據
newptr->next=NULL;
if(HL=NULL) //如果是空鏈表，則表頭指針指向新節點
HL=_newptr_____.
LNode*P=HL;
While(P->next!=NULL)//循環找到鏈表的尾部
___P=P->next_____;
p->next=newptr;
}
}

2二分查找的遞歸演算法。

Int Binsh(ElemType A[],int low,int high,keyTypeK)
{
If____(low<=hign)______________{
int mid=(low+high)/2;
If(__K==A[mid]____)return mid;
else if (K<A[mid],key)
return Binsch(A,low,mid-1,K);
else return__Binsch(A,mid+1,hign,K)_____________;
}
else_return -1__________; //返回-1表示沒有找到
}

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

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

⑸ 二分查找演算法實現（圖解）與實例

當我們要從一個序列中查找一個元素的時候，二分查找是一種非常快速的查找演算法，二分查找又叫折半查找。

它對要查找的序列有兩個要求，一是該序列必須是有序的（即該序列中的所有元素都是按照大小關系排好序的，升序和降序都可以，本文假設是升序排列的），二是該序列必須是順序存儲的。

如果一個序列是無序的或者是鏈表，那麼該序列就不能進行二分查找。之所以被查找的序列要滿足這樣的條件，是由二分查找演算法的原理決定的。

二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。

二分查找能應用於任何類型的數據，只要能將這些數據按照某種規則進行排序。然而，正因為它依賴於一個有序的集合，這使得它在處理那些頻繁插入和刪除操作的數據集時不太高效。這是因為，對於插入和操作來說，為了保證查找過程正常進行，必須保證數據集始終有序。相對於查找來說，維護一個有序數據集的代價更高。此外，元素必須存儲在連續的空間中。因此，當待搜索的集合是相對靜態的數據集時，此時使用二分查找是最好的選擇。

二分查找演算法的原理如下：

二分查找之所以快速，是因為它在匹配不成功的時候，每次都能排除剩餘元素中一半的元素。因此可能包含目標元素的有效范圍就收縮得很快，而不像順序查找那樣，每次僅能排除一個元素。

二分查找法實質上是不斷地將有序數據集進行對半分割，並檢查每個分區的中間元素。

此實現過程的實施是通過變數left和right控制一個循環來查找元素（其中left和right是正在查找的數據集的兩個邊界值）。

二分查找的時間復雜度取決於查找過程中分區數可能的最大值。對於一個有n個元素的數據集來說，最多可以進行O(㏒₂n)次分區。對於二分查找，這表示最終可能在最壞的情況下執行的檢查的次數：例如，在沒有找到目標時。所以二分查找的時間復雜度為O(㏒₂n)。

參考：
https://www.html.cn/qa/other/23018.html

https://www.cnblogs.com/idreamo/p/9000762.html

⑹ c++二分查找（遞歸法）為什麼答案錯誤

數組的i未經賦值。聲明的數組是不確定的。

其實，程序沒有使用題目規定的二分查找，和遞歸的方法。

#include<cstdio>
inta[1000000];
intbsearch(intlow,inthigh,intx)
{intm;
if(low>high)return-1;
m=(low+high)/2;
if(a[m]==x)returnm+1;
if(a[m]>x)returnbsearch(low,m-1,x);
elsereturnbsearch(m+1,high,x);
}
usingnamespacestd;
intmain()
{intn=10,x,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&x);
printf("%d
",bsearch(0,n-1,x));
return0;
}

⑺ C語言 二分法查找 排序問題

a.txt:讀入數據

b.txt: 寫入排序數據

c.txt: 寫入查找結果

#include<stdio.h>

constintmaxn=1000;
intnum[maxn],n;


voidswap(int*x,int*y){
*x^=*y;
*y=*x^*y;
*x=*x^*y;
}

voidfinput(){
printf("--------
readdatafroma.txt
--------

");
FILE*fin=fopen("a.txt","r");
n=0;
while(fscanf(fin,"%d",&num[n])!=EOF){
n++;
}
fclose(fin);
}


voidbubble(){
printf("--------
startbubblingsortalgorithm
");
for(inti=n-1;i>0;--i){
for(intj=0;j<i;++j){
if(num[j]>num[j+1]){
swap(&num[j],&num[j+1]);
}
}
}

printf("writetheresultofsortinb.txt
--------

");
FILE*fout=fopen("b.txt","w");
for(inti=0;i<n;++i){
fprintf(fout,"%d
",num[i]);
}
fclose(fout);
}

intrbesearch(intlow,inthigh,intv){
//recursivebinarysearch
//returntheindexofv.ifnotexists,return-1.
if(low==high){
if(num[low]==v)returnlow;
return-1;
}
if(num[low]==v)returnlow;
intmid=(low+high)/2;
if(num[mid]<v){
returnrbesearch(mid+1,high,v);
}
else{
returnrbesearch(low,mid,v);
}
}

intnrbesearch(intlow,inthigh,intv){
//non-recursivebinarysearch
//returntheindexofv.ifnotexists,return-1.
while(low<high){
intmid=(low+high)/2;
if(num[mid]<v){
low=mid+1;
}
else{
high=mid;
}
}
if(low==high&&num[low]==v){
returnlow;
}
return-1;
}


voidsearch(){
printf("--------
");
printf("Startsearch.
");
printf("Theresultswillbewritteninc.txt
");
printf("pleaseinputanum.ifnum=-123456,quit.
");

FILE*file=fopen("c.txt","w");
while(true){
intv;
scanf("%d",&v);
if(v==-123456)break;

intrb=rbesearch(0,n-1,v);
intnrb=nrbesearch(0,n-1,v);

fprintf(file,"input:%d
",v);
fprintf(file,":%d
",rb);
fprintf(file,"theresultofnon-recursivebinarysearch:%d

",nrb);

printf(":%d
",rb);
printf("theresultofnon-recursivebinarysearch:%d

",nrb);
}
fclose(file);

}

intmain(){
finput();
bubble();
search();
return0;
}

⑻ 用二分查找演算法查詢某學生成績

/*這是我自己寫的二分查找演算法，用遞歸實現：在已按非降序排序的數組arr[0..length-1]中從位置startPos到endPos查找num這個值，返回值為下標的值，若沒找到則返回-1。*/
int binarySearch(int *arr,int num,int startPos,int endPos)
{
if((startPos >= endPos) && (*(arr+startPos) != num))
{
return -1;
}
else
{
int j = (startPos+endPos)/2;

if(*(arr+j) == num)
{
return j;
}
else
{
if(*(arr+j) > num)
{
return binarySearch(arr,num,startPos,j-1);
}
else
{
return binarySearch(arr,num,j+1,endPos);
}
}
}
}

⑼ 二分查找演算法

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

⑽ 二分查找偶數

奇數的時候：就是中間值

偶數的時候：取n/2取整，實際上剩下的序列是 索引為取整左邊的序列。
# 二分查找
# 方法一：遞歸
def binary_search(alist, item):
# 數列長度
n = len(alist)
# 遞歸的結束條件
if n == 0:
return False

# 中間值
# // 是取整
mid = n // 2

if item == alist[mid]:
return True
elif item < alist[mid]:
return binary_search(alist[0:mid], item)
elif item > alist[mid]:
return binary_search(alist[mid + 1:], item)

if __name__ == '__main__':
alist = [1, 2, 3, 4, 5]
print(binary_search(alist, 3))