线性表（a1,a2,a3……an）中的元素递增有序且按顺序存储于计算机中，设计一算法，在表中查找数组为x的元素，若找到则将其与后继元素位置交换，找不到则插入x并依然递增有序 思路：为了加快查找速度，这里采用折半查找法
#include<stdio.h> #include<stdlib.h> #define LIST_INIT_SIZE 100 #define LISTINCREMENT 20 typedef struct { int *elem; int length; int listsize; }SqList; bool InitList_Sq(SqList &L); void PrintElem_Sq(SqList L); void SearchExchangeInsert(SqList &L, int x); int main() { int x; SqList L; InitList_Sq(L); L.elem[0] = 0; L.elem[1] = 2; L.elem[2] = 4; L.elem[3] = 6; L.elem[4] = 8; L.length = 5; printf("请输入要在顺序表中查找的元素x："); scanf("%d", &x); SearchExchangeInsert(L, x); PrintElem_Sq(L); return 0; } bool InitList_Sq(SqList &L) { L.elem =(int*)malloc(LISTINCREMENT*sizeof(int)); if(!L.elem) return false; L.length = 0; L.listsize = LIST_INIT_SIZE; return true; } void PrintElem_Sq(SqList L) { if(L.length == 0) printf("顺序表为空"); else for(int i = 0; i < L.length; i ++) printf("%d ", L.elem[i]); } void SearchExchangeInsert(SqList &L, int x)//二分查找 { int low = 0,high = L.length-1, mid; int i; while(low <= high) { mid = low + (high - low) / 2; if(L.elem[mid] == x) break; else if (L.elem[mid] < x) low = mid + 1; else high = mid - 1;//? } if (L.elem[mid] == x && mid != L.length-1) { int t = L.elem[mid]; L.elem[mid] = L.elem[mid + 1]; L.elem[mid + 1] = t; } if (low > high) { L.length ++; for (i = L.length-1; i > high; i--) L.elem[i + 1] = L.elem[i]; L.elem[i + 1] = x; } }