有一个已排好序的数组(如{5, 12, 22, 34, 45, 55, 67, 78, 89, 98}),要求输入一个数后,按原来排序的规律将它插入到该数组中,然后求采用二分法查找新插入的数所在位置(下标)。假设:所有的数都互不相同。
先插入,然后二分查找
#include <stdio.h>
void insert(int *a,int n,int m)
{
int i=0;
for(i=0;i<n;i++)
{
if(m < *(a+i))
{
for(int j=n;j>i;j--)
*(a+j) = *(a+j-1);
*(a+i) = m;
break;
}
}
if(i==n)
*(a+n-1) = m;
}
int search(int *a,int n,int m)
{
int start = 0,end = n-1;
while(start <= end)
{
int mid = (start+end)/2;
if(a[mid] == m)
return mid;
if(a[mid] < m)
start = mid + 1;
else
end = mid - 1;
}
return -1;
}
int main()
{
int a[11] = {5,12, 22, 34, 45, 55, 67, 78, 89, 98};
int n;
scanf("%d",&n);
insert(a,10,n);
for(int i=0;i<11;i++)
printf("%d ",a[i]);
printf("\n下标为:%d",search(a,11,n));
}