（本博客旨在个人总结回顾）
一、概念
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
二、实现
// BinarySearch.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
* @name BinarySearchRecursion
* @brief 二分查找递归实现
* @param [in] int * pArray 查找的有序数组(升序)
* @param [in] int nBegin 查找数组的起始下标
* @param [in] int nEnd 查找数组的结束下标
* @param [in] int nKey 查找的目标值
* @return int -1为目标数组无nKey值，其他值数组元素值为nKey的下标
*/
int BinarySearchRecursion(int* pArray, int nBegin, int nEnd, int nKey)
{
if (NULL == pArray || nBegin > nEnd)
{
return -1;
}
int nMid = (nBegin + nEnd) / 2;
if (pArray[nMid] == nKey)
{
return nMid;
}
else if (pArray[nMid] > nKey)
{
return BinarySearchRecursion(pArray, nBegin, nMid - 1, nKey);
}
else
{
return BinarySearchRecursion(pArray, nMid + 1, nEnd, nKey);
}
}
/*
* @name BinarySearchUnrecursion
* @brief 二分查找非递归实现
* @param [in] int * pArray 查找的有序数组(升序)
* @param [in] int nBegin 查找数组的起始下标
* @param [in] int nEnd 查找数组的结束下标
* @param [in] int nKey 查找的目标值
* @return int -1为目标数组无nKey值，其他值数组元素值为nKey的下标
* @return int
*/
int BinarySearchUnrecursion(int* pArray, int nBegin, int nEnd, int nKey)
{
if (NULL == pArray || nBegin > nEnd)
{
return -1;
}
int nMid = -1;
while (nBegin <= nEnd)
{
nMid = (nBegin + nEnd) / 2;
if (pArray[nMid] == nKey)
{
return nMid;
}
if (pArray[nBegin] <= nKey && pArray[nMid] > nKey)
{
nEnd = nMid - 1;
}
else if (pArray[nMid] < nKey && pArray[nEnd] >= nKey)
{
nBegin = nMid + 1;
}
else
{
return -1;
}
}
return -1;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[10] = {};
int nLength = sizeof(a) / sizeof(a[0]);
cout << "升序数组：" << endl;
for (int i = 0; i < nLength; i++)
{
a[i] = i;
cout << a[i] << " ";
}
cout << endl << "输入查找值：";
int nKey = -1;
cin >> nKey;
int nIndex = BinarySearchRecursion(a, 0, nLength-1, nKey);
if (nIndex != -1)
{
cout << endl << "数组中有该值，下标为：" << nIndex << endl;
}
else
{
cout << endl << "数组中无该值" << endl;
}
system("pause");
return 0;
}
执行结果：
