二分法查找法

二分法，又称折半查找法，从一个已经正向排序好的数列中查找某元素的位置。

具体代码、注释如下。

// 采用循环方式的二分法查找 int BinarySearch(int r[], int nCount, int nVal) { int nLowIdx = 0, nEndIdx = nCount - 1; while(nLowIdx < nEndIdx) { int nMidIdx = (nLowIdx + nEndIdx) / 2; // 找到中间数 if(r[nMidIdx] == nVal) // 如果中间数=需要查找的值，直接返回 { return nMidIdx; } else if(nVal < r[nMidIdx]) // 如果此数小于中间数 { nEndIdx = nMidIdx - 1; // 限定左区间 } else if(nVal > r[nMidIdx]) // 如果此时大于中间数 { nLowIdx = nMidIdx + 1; // 限定右区间 } } return -1; } // 采用递归方式的二分法查找 int BinarySearch(int r[], int nBeginIdx, int nEndIdx, int nVal) { if(nBeginIdx > nEndIdx) // 起始索引大于结束索引，则表示没有查找到该数值 { return -1; } int nMidIdx = nBeginIdx + nEndIdx; // 获得中间数的索引号 int nMidVal = r[nMidIdx]; // 获得中间数的值 if(nMidVal == nVal) // 找到中间数 { return nMidIdx; } else if(nVal < nMidVal) // 数值小于中间数 { return BinarySearch(r, nBeginIdx, nMidIdx - 1, nVal); // 在左区间内继续查找 } else if(nVal > nMidVal) { return BinarySearch(r, nMidIdx + 1, nEndIdx, nVal); // 在右区间内继续查找 } }