C++中用二分法，在数组中找出一个输入的数后删除

Question

请各位用C++写处一段符合下列要求的代码：

一个已经排好序的数组，输入一个数，利用二分法把这个数从原数组中删除，数组顺序保持不变。如原数组为1,3,5,7,9,11,13,15,17,19，待删除的数为13，则输出为1,3,5,7,9,11,15,17,19。
二分法：每次都是判断中间的数是否满足要求，若满足则删除，若不满足，则把该数当作边界，然后再找中点。例如这一题，第一次的是10个数的中点，为11，发现11<13，则找11-19的中点15，发现15>13，再找11-15的中点13，正好，则删除。

Answer 1

我把函数给你编好了~
template <class ElemType, class KeyType,int n>
bool BinSerach(ElemType elem[n],KeyType key)
// 操作结果: 在有序表中查找其关键字的值等于key的记录,如查找成功,则删除此记录并返回TRUE
//否则返回FALSE
{
int low = 0, high = n -1; // 查找区间初值

while (low <= high)
{
int mid = (low + high) / 2; // 查找区间中间位置
if (key == elem[mid])
{ // 查找成功
for(int i=mid;i!=n-1;++i)
{
elem[i]=elem[i+1];
}
return true;
}
else if (key <= elem[mid])
{ // 继续在左半区间进行查找
high = mid - 1;
}
else
{ // 继续在右半区间进行查找
low = mid + 1;
}
}

return false; // 查找失败
}

Answer 2

#include <iostream>
using namespace std;

//f在a[0]到a[n-1]之间查找x的位置,并返回这个位置的下标
//找不到则返回-1
int f(int a[],int n,int x)
{
int left,right,middle;
left=0;right=n;
while(left<=right)
{
middle=(left+right)/2;
if(x>a[middle]) left=middle+1;
else if(x<a[middle]) right=middle-1;
else return middle;
}
return -1;
}

main()
{
int a[]={1,3,5,7,9,11,13,15,17,19};
int x,i,pos;
scanf("%d",&x);
pos=f(a,sizeof(a)/sizeof(int),x);
for(i=0;i<sizeof(a)/sizeof(int);i++)
{
if(i!=pos) cout<<a[i]<<' ';
}
}

Answer 3

#include<iostream>
using namespace std;
int FindItem (int *p,int n,int item)
{
int mid=n/2;
while(p[mid]!=item)
{
if(mid+1>n-1 || mid-1<0)
{
cout<<"there is no this item!"<<endl;
exit(1);
}
if(p[mid]>item)mid=(mid-1)/2;
else mid=(mid+n)/2;
}
return mid;
}
int main()
{
int a[10];
int b;
for(b=0;b<=9;b++)
cin>>a[b];
int pos=FindItem(a,10,9);
cout<<pos<<endl;
return 0;
}

参考资料：应该很简单，不过没有完善功能，只是为了说明怎么二分查找到待删除的元素

Answer 4

#include<iostream>
using namespace std;
#define len_s 10

int binary_search(const int *s,int firstp,int lastp,const int input_value)//return the place of input_value in s[]
{
if(firstp > lastp)
{
return -1;
}

int middle = (int)(firstp + lastp) / 2;

if(input_value == *(s + middle))
{
return (int)(firstp + lastp) / 2;
}
else if(input_value > *(s + middle))
{
binary_search(s, middle + 1, lastp, input_value);
}
else
{
binary_search(s, firstp, middle - 1, input_value);
}
}

int *del_input(int *s,const int input_value)
{
int val_place = binary_search(s, 0, len_s, input_value);

if( val_place == -1)
{
cout<<"input value you want to be deleted not exist"<<endl;
return s;
}

for(int i = val_place; i < len_s; ++i)
{
*(s + i) = *(s + i + 1);
}
return s;
}

void main()
{
int *s = new int[len_s];
int i = 0;

for(i = 0; i < len_s; ++i)
{
*(s + i) = 2 * i + 1;
}

int input_value = 0;
cout<<"input value you want to be deleted:";
cin>>input_value;
s = del_input(s, input_value);

for(i = 0; i < len_s-1 ; ++i)
{
cout<<*(s + i)<<" ";
}
cout<<endl;
delete []s;
s = NULL;
}
我也写了一个