- 科技
- 数据结构——折半查找【并插入元素】（C语言）
二分查找（折半查找）
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 10010
int RecurSearch(int A
[],int low
,int high
,int key
){
int flag
=0;
while(low
<=high
){
int mid
=(low
+high
)/2;
if(A
[mid
]==key
){
printf("元素下标为：%d，查找成功！\n",mid
);
flag
=1;
break;
}
if(key
>A
[mid
])
low
=mid
+1;
else if(key
<A
[mid
])
high
=mid
-1;
}
if(!flag
)
printf("查找失败！\n");
}
void display(int A
[],int n
){
for(int i
=0;i
<n
;i
++){
printf("%d ",A
[i
]);
}
printf("\n");
}
int main(){
int n
;
printf("输入元素个数：");
scanf("%d",&n
);
int A
[MAXSIZE
];
for(int i
=0;i
<n
;i
++){
int elem
;
printf("输入元素：");
scanf("%d",&elem
);
A
[i
]=elem
;
}
display(A
,n
);
int low
,high
,key
;
low
=0;
high
=n
-1;
printf("输入查找元素：");
scanf("%d",&key
);
RecurSearch(A
,low
,high
,key
);
return 0;
}
折半查找并在对应位置插入元素
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 10010
void BinInsert(int A
[],int &n
,int key
){
int low
,high
,location
=-1,flag
;
int mid
;
low
=0,flag
=0,high
=n
-1;
while(low
<high
){
mid
=(low
+high
)/2;
if(A
[mid
]==key
){
printf("元素下标为：%d，查找成功！\n",mid
);
location
=mid
;
flag
=1;
break;
}
if(key
>A
[mid
])
low
=mid
+1;
else if(key
<A
[mid
])
high
=mid
-1;
}
printf("location=%d\n",location
);
if(location
<0)
location
=mid
-1;
else
location
=mid
;
int i
;
for(i
=n
-1;i
>=location
;i
--){
A
[i
+1]=A
[i
];
}
A
[++i
]=key
;
n
++;
}
void display(int A
[],int n
){
for(int i
=0;i
<n
;i
++){
printf("%d ",A
[i
]);
}
printf("\n");
}
int main(){
int n
;
printf("输入元素个数：");
scanf("%d",&n
);
int A
[MAXSIZE
];
for(int i
=0;i
<n
;i
++){
int elem
;
printf("输入元素：");
scanf("%d",&elem
);
A
[i
]=elem
;
}
display(A
,n
);
int low
,high
,key
;
low
=0;
high
=n
-1;
printf("折半查找，并插入元素\n");
scanf("%d",&key
);
BinInsert(A
,n
,key
);
display(A
,n
);
return 0;
}
Processed:
0.010, SQL:
8
