二分查找递归算法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))