二分

int Binary_Search(vector<int> A,int key){int n=A.size();int low=0,high=n-1,mid;while(low<=high){mid=(low+high)/2;if(A[mid]==key)return mid;else if(A[mid]>key)high=mid-1;elselow=mid+1;	}return -1;
}

折半插入排序

——找到第一个$\ge$tem的元素

void InsertSort(vector<int> A){int n=A.size();int low,high,mid;for(int i=1;i<=n;i++){int tem=A[i];low=1;high=i-1;while(low<=high){mid=(low+high)/2;if(A[mid]>tem)high=mid-;elselow=mid+1;}for(int j=i--1;j>=high+1;j--)A[j+1]=A[j];A[high+1]=tem;}