算法——二分法查找与二分法插入排序
1.二分法查找（binarySearch）
众所周知，古代有一种查找方式：100个数内通过五次得出一个人心里想的数字，这便是二分法查找。
二分法查找，也称为折半法查找，是一种在有序数组中查找特定元素的搜索算法。以下便是其思路：
1）在数组两端插入两个区域限制数据，然后从数组的中间元素开始搜索，如果该元素是目标元素，则搜索过程结束，若不为目标元素，则开始执行下一步
2）若目标元素小于中间元素((最大值+最小值)/2)，则右节点移至中间元素，若目标元素大于中间元素,则左节点移至中间元素。该步骤结束后开始进行下一次查找，重复（1）的操作。
3）直到左节点与右节点指向同一个元素，那么该元素为目标元素，至此跳出循环。
有了以上思路，便可以写出代码：
#include<iostream>
using namespace std;
void halfSerch(int* a, int number, int n)
{
int min = 0;
int max = n - 1;
int timenumber = 0;
while (min<max)
{
//获取中间点
int mid = (max + min) / 2;
//获取中间节点成功，跳出循环，得到查找的次数
if (a[mid] == number)
{
timenumber++;
cout << "查找了" << timenumber << "次" << endl;
cout << "查找到的最终值为" << a[mid] << endl;
break;
}
//中间值小于设定值，最小值变为中间值+1，查找次数+1
else if (a[mid] < number)
{
min = mid + 1;
timenumber++;
}
//中间值小于设定值，最大值变为中间值-1，查找次数+1
else if (a[mid]>number)
{
max = mid - 1;
timenumber++;
}
}
}
int main()
{
int a[10];
int n, number;
cout << "输入数组大小";
cin >> n;//(n<=10)
for (int i = 0; i < n; i++)
{
cout << "输入第"<<i+1<<"个数组的值";
cin >> a[i];
}
cout << "输入设定的值";
cin >> number;
halfSerch(a, number, n);
}
运行结果：
得到该算法后，可以算出时间复杂度：
由该题意可得：数据长度为N，每次查找后减半。
第一次为：N/2
第二次为：N/4
.
.
.
第n次为：N/(2^n)
最差的情况是:最终数据长度为1，所以有：
N/(2^n) = 1;
所以可得出n=log2(N);
而最好的情况是第一次
因此该算法时间复杂度位O(log2(N))
2.二分法插入排序(折半法排序)
二分法插入排序与插入排序在本质上都没有区别，都是从无序序列中取出数据和有序序列进行对比，放到合适位置。
但是它俩的区别在于：
虽然两者都是对待排序的数，插入到前面已经排好序的数组中，并且时间复杂度都为O(1)~O(n^2)，但是相比于直接插入排序，二分法插入排序减少了比较的次数，平均的性能优于直接插入排序。
程序如下：
#include<iostream>
using namespace std;
//二分法插入排序
void insertBinary(int* a, int n){
int i, j, tmp;
int low, mid, high;
for (i = 1; i<n; i++){
tmp = a[i];
low = 0; high = i - 1;
/* 1.寻找插入位置J */
while (low <= high){
mid = (low + high) / 2;
if (tmp>a[mid]) low = mid + 1; //如果取的数据比中间的大,则说明需要在mid右边寻找位置J
else high = mid - 1;
}
/* 2.后移插入位置 */
//从位置i到位置J(low/high)依次后移动一位
for (j = i; j>low; j--){
a[j] = a[j - 1];
}
a[low] = tmp;
}
}
int main()
{
int a[10] = { 5, 2, 1, 3, 9, 4, 6, 7, 0, 8 };
insertBinary(a, 10);
for (int i = 0; i < 10; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
运行结果：
对于比较少的数据，二分法插入排序体现不到很多优点，但是若有大量的数据需要排序，则二分法插入排序相较于插入排序更能优化运算性能。