## 问题描述 > 线性表(a1,a2,a3,...,an)中元素递增有序，且按顺序存储于计算机内。要求设计一算法完成用最少时间在表中查找数据值为x的元素；若找到，将其与后继元素位置交换；若找不到将其插入到表中，使表中的元素仍递增有序 ## 算法思想 > 本题递增有序，为了在最少的事件内完成指定数据x的查找，那么我们可以采用折半查找的思想查找x，如果找到，那么与后继元素交换一次，如果找不到则顺序插入便可。 ## 算法描述 ~~~ int FindDI(SqList *L, ElemType x) { int low=0, high=L->length-1; int mid; //折半查找 while(low<high){ mid=(low+high)/2; if(L->data[mid]==x){ break; }else if(L->data[mid]<x){ low=mid+1; }else{ high=mid-1; } } //已找到，与后继元素位置交换 if(L->data[mid]==x&&L->data[mid]!=L->length-1){ ElemType temp; temp=L->data[mid]; L->data[mid]=L->data[mid+1]; L->data[mid+1]=temp; return mid+1; } //未找到，插入该元素，并且使表中的元素仍递增有序 if(low>high){ int i; for(i=L->length;i>mid;i--){ L->data[i]=L->data[i-1]; } L->data[i]=x; L->length=L->length+1; return -1; } return 0; } ~~~ 具体代码见附件 ## 附件 ~~~ #include<stdio.h> #define MaxSize 100 typedef int ElemType; typedef struct{ ElemType data[MaxSize]; int length; }SqList; int FindDI(SqList*, ElemType); void Print(SqList*); int main(int argc,char *argv[]) { SqList SL; ElemType e=4; SL.length=10; for(int i=0;i<SL.length;i++){ SL.data[i]=2*i+1; } Print(&SL); int flag=FindDI(&SL,e); if(flag==-1){ printf("Find fail!,It will be instered the true position\n"); Print(&SL); }else{ printf("Find success!\n"); printf("It is posed %dth, It will swap with next number!\n", flag); Print(&SL); } return 0; } int FindDI(SqList *L, ElemType x) { int low=0, high=L->length-1; int mid; while(low<high){ mid=(low+high)/2; if(L->data[mid]==x){ break; }else if(L->data[mid]<x){ low=mid+1; }else{ high=mid-1; } } if(L->data[mid]==x&&L->data[mid]!=L->length-1){ ElemType temp; temp=L->data[mid]; L->data[mid]=L->data[mid+1]; L->data[mid+1]=temp; return mid+1; } if(low>high){ int i; for(i=L->length;i>mid;i--){ L->data[i]=L->data[i-1]; } L->data[i]=x; L->length=L->length+1; return -1; } return 0; } void Print(SqList *L) { for(int i=0;i<L->length;i++){ printf("%4d",L->data[i]); } printf("\n"); } ~~~