# 常见的查找算法

Java 算法 C/C++ 15300 次浏览

```/**
*  在s[0]-s[n-1]中顺序查找关键字为Key的记录 ,查找成功时返回该记录的下标序号；失败时返回-1
*/
int SequelSearch(elemtype s[], keytype Key, int n){
int i;
i = 0;
while (i < n && s[i].Key != Key)
i++;

if (s[i].Key == Key)
return i;
else
return -1;
}```

1.递归实现

```/**
* 在下届为low，上界为high的数组a中折半查找数据元素x
*/
int binarySearch(elemtype a[], elemtype x, int low, int high) {
int mid;
if (low > high)
return -1;
mid = (low + high) / 2;
if (x == a[mid])
return mid;
if (x < a[mid])
return (binarySearch(a, x, low, mid - 1));
else
return (binarySearch(a, x, mid + 1, high));
}```

2.非递归实现

```int binarySearch(elemtype a[], keytype key, int n) {
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid].key == key)
return mid;
else if (a[mid].key < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}```

```typedef int keytype;

typedef struct {
keytype Key;
}elemtype;

typedef struct{
keytype Key;
}indextype;

/**
* 分块查找关键字为Key的记录。索引表为ls[0]-ls[m-1],顺序表为s，块长为l
*/
int IndexSequelSearch(indextype ls[],elemtypes[],int m,int l,keytype Key){
int i,j;
/*在索引表中顺序查找*/
i=0;
while(i<m&&Key>ls[i].Key)i++;

if(i>=m)
return -1;
else{
/*在顺序表中顺序查找*/
j++;

if(Key==s[j].Key)
return j;
else
return -1;
}
}```

1.二叉树查找算法

a.非递归算法

```btree *search(btree *b,int x){
/*在二叉树b中查找x的过程*/
if(b=NULL)
return(NULL);

else{
if(b->data==x)
return(b);
if(x<b->data)
return(search(b->left));
else
return(search(b->right));
}
}```

b.递归算法

```bsnodetype *Search(bsnodetype *bt,keytype Key){
/*在二叉树bt中查找元素为Key的元素*/
bsnodetype *p;
if(bt==NULL)
return(bt);

p=bt;
while(p->Key!=Key){
if(Key<p->Key)
p=p->Lchild;
else
p=p->Rchild;
if(p==NULL)
break;
}
return(p);
}```

2.生成二叉树

a、向一个二叉树b中插入一个结点s的函数如下：

```void insert(b,s){
btree *b,*s;

if(b==NULL)
b=s;
else if(s->data==b->data)
return();
else if(s->data<b->data)
insert(b->left,s);
else if(s->data>b->data)
insert(b->right,s);
}```

b、创建二叉树

```void create(btree *b){
int x;
btree 8s;
b==NULL;

do{
scanf("%d",&x);
s=(bnode *)malloc(sizeof(bnode));
s->data=x;
s->left=NULL;
s->right=NULL;
insert(b,s);
}while(x!=-1);
}```

c、从二叉树中删除一个结点

```bsnodetype *Delete(bsnodetype *bt,keytype Key){/*在bt为根结点的二叉树中删除值为Key的结点*/

bsnodetype *p,*q;
if(bt->Key==Key){
/*bt的左右子树均为空*/
if(bt->Lchild==NULL&&bt->Rchild==NULL){
free(bt); /*删除叶结点*/
return(NULL);
}else if(bt->Lchild==NULL){ /*bt的左子树为空*/
p=bt->Rchild;
free(bt);
return(p);
}else if(bt->Rchild==NULL){/*bt的右子树为空*/
p=bt->Lchild;
free(bt);
return(p);
}else{
p=q=bt->Rchild;
while(p->Lchild!=NULL)
p=p->Lchild;
p->Lchild=bt->Lchild;
free(bt);
return(q);
}
}

/*在bt->Lchild为根结点的二叉树中删除值为Key的结点*/
if(bt->Key>Key&&bt->Lchild!=NULL)
bt->Lchild=Delete(bt->Lchild,Key);

/*在bt->Rchild为根结点的二叉树中删除值为Key的结点*/
if(bt->Key<Key&&bt->Rchild!=NULL)
bt->Rchild=Delete(bt->Rchild,Key);

return(bt);
}```