## 問題描述 > 線性表(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"); } ~~~