经典面试题总结 —— Binary Search 及其变种
二分查找是在技术面试中经常出现的题目，首先这种题目考察思路，另外因为代码一般很短----不会超过50行。所以很适合做技术笔试，或者面试之类的题目出现。
之前做过一些题目，很多是BS算法的变种，我这里给出几个例子，算是做一个总结吧。
1.1. 最普通的BS算法就是给定一个排好序的数组，然后查找一个数是否在数组内，如果在给出下标，如果不在则返回-1.
bool SearchInRowColSortedMatrix(const int data[], int nRow, int nCol, int query, int &tRow, int &tCol){ int iRow, iCol; iRow = 0; iCol = nCol - 1; int t; while(iRow < nRow && iCol >= 0) { t = data[iRow * nCol + iCol];//get the current data. if( t == query) //find it { tRow = iRow; tCol = iCol; return true; } else if( t < query) // eleminate the rest of the elements in the current row, who are less than t. { iRow++; } else //eleminate all the rest elements in current col, who are greater than t. { iCol--; } } return false;}上面的代码可能有一些地方有bug， 虽然我做了一些测试，包括穷举所有内部元素的 正测试，还有不在查找数组中的反测试。 这些代码确实很容易出bug，对于一些大公司如MS等比较看重代码，要求bug-free的公司可能经常作为考题，来考察现场编程能力。 不过自己依然很水，还需要努力，努力写出bug-free的code