题目描述：
线性表中元素递增有序且按顺序存储与计算机内。要求设计一算法完成：
（1）用最少时间在表中查找数值为x的元素
（2）若找到将其与后继元素位置交换
（3）若找不到，将其插入表中并使表中元素仍递增有序
思路：
用二分查找法进行查找，时间复杂度为O（logn）。
代码：
int flag=0;//默认没找到元素x
void swapOrInsert(int a[],int &length,int low,int high,int x){int index=halfSearch(a,low,high,x);if(flag==1){//进行交换if(index<length-1){swap(a[index],a[index+1]);}else{cout<<"找到的元素是末尾元素，无法进行交换"<<endl;}}else{//进行插入insert(a,length,index,x);}
}int halfSearch(int a[],int low,int high,int x){
//经验来说，二分查找最后返回一个mid下标，再用其他函数对mid下标位置周围的元素进行操作int mid;while(low<=high){mid=(low+high)/2;if(a[mid]==x){flag=1;return mid;}else if(a[mid]>x)high=mid-1;elselow=mid+1;}return mid;
}void swap(int &a,int &b){int temp=a;a=b;b=temp;
}void insert(int a[], int &length,int index,int e){for(int i=length-1;i>=index;i--){a[i+1]=a[i];}a[index]=e;length++;
}
测试：
#include<stdio.h>
#include <stdlib.h>
#include<math.h> //数学函数，求平方根、三角函数、对数函数、指数函数...#define MAXSIZE 100//用于使用c++的输出语句
#include<iostream>
using namespace std;int halfSearch(int a[],int low,int high,int x);
void swap(int &a,int &b);
void swapOrInsert(int a[],int &length,int low,int high,int x);
void insert(int a[], int &length,int index,int e);int flag=0;//默认没有找到对应元素
void main(){int arr[MAXSIZE]={1,2,4,5,6,8,9};int length=7;int x=3;int low=0;int high=6;//1.找到并且不是最后一个元素swapOrInsert(arr,length,low,high,x);cout<<flag<<endl;for(int i=0;i<length;i++){cout<<arr[i]<<"\t";}//2.找到并且是最后一个元素//pass//3.没找到，进行插入操作//pass
}//在一个函数A中调用函数B，首先满足B的所有参数，其次再考虑增加其他参数
void swapOrInsert(int a[],int &length,int low,int high,int x){int index=halfSearch(a,low,high,x);if(flag==1){//进行交换if(index<length-1){swap(a[index],a[index+1]);}else{cout<<"找到的元素是末尾元素，无法进行交换"<<endl;}}else{//进行插入insert(a,length,index,x);}
}int halfSearch(int a[],int low,int high,int x){
//经验来说，二分查找最后返回一个mid下标，再用其他函数对mid下标位置周围的元素进行操作int mid;while(low<=high){mid=(low+high)/2;if(a[mid]==x){flag=1;return mid;}else if(a[mid]>x)high=mid-1;elselow=mid+1;}return mid;
}void swap(int &a,int &b){int temp=a;a=b;b=temp;
}void insert(int a[], int &length,int index,int e){for(int i=length-1;i>=index;i--){a[i+1]=a[i];}a[index]=e;length++;
}