学习了一节C++视频课程, 把老师的例子, 改了一下, 加深理解
#include <iostream>
#include <vector>
using namespace std;void insert2vec(vector<int> &v, int n)
{vector<int>::iterator lo=v.begin(), hi=v.end()-1;vector<int>::iterator mi=v.begin()+(hi-lo)/2;//二分法插入, 新成员比中间的大, 就要插入后半截, 否则插入前半截// 分到最后, mi==lo==hi, 指向同一位置, 这个位置前面的数<=n, 后面的数>=n // 这个位置上的数, <n,=n,>n都可能while (hi>lo){//输出指针指向的位置cout<<"lo->"<<1+lo - v.begin()<<"\t"; cout<<"mi->"<<1+mi - v.begin()<<"\t";cout<<"hi->"<<1+hi - v.begin()<<"\t\n";/*//三种情况不再继续二分,if (n==*mi){v.insert(mi+1, n);return;}else if (n<*lo){v.insert(lo, n);return;}else if (n>*hi){v.insert(hi+1, n);return;}*///二分法移动lo或hi, 计算miif (n<*mi)hi= mi==lo?lo:mi-1;elselo=mi+1;//二分法移动lo或hi, 计算mi/*if (n>*mi) //判断大于, 效率低于判断小于lo=mi+1;elsehi= mi==lo?lo:mi-1;*/mi=lo+(hi - lo)/2;}//输出指针指向的位置cout<<"lo->"<<1+lo - v.begin()<<"\t"; cout<<"mi->"<<1+mi - v.begin()<<"\t";cout<<"hi->"<<1+hi - v.begin()<<"\t\n";//这时hi===mi==lo if (n<*lo)v.insert(lo, n);else v.insert(lo+1, n);return;//二分法, {3,5,7}, 插入6时, 与中间5比较, 则队列缩短为{7}, 同时lo==mi==hi
}int main(void){vector<int> shuzi;vector<int>::iterator it;int i=0; //用7次循环, 分别测试 1, 8, 5, 4, 6, 3, 7//单步debug, 验证理解for (i=0;i<7;i++){shuzi.clear();shuzi.push_back(3);//shuzi.push_back(5);shuzi.push_back(5);shuzi.push_back(5);shuzi.push_back(7);cout<<"第"<<i+1<<"次测试:\n";for (it=shuzi.begin(); it!=shuzi.end(); it++)cout<<*it<<"\t";cout<<"\n请输入要插入的数字:\n";//在数组中插入一个数字int n;cin>>n;insert2vec(shuzi, n);for (it=shuzi.begin(); it!=shuzi.end(); it++)cout<<*it<<"\t";cout<<"\n\n";}return 0;
}