经典面试题总结 —— 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

2楼CarzyStarry昨天 22:27

代码还缺少了非法输入的检测

Re: hopeztm昨天 22:56

恩是的，应该在最前面都是 加上这个特殊情况回复CarzyStarry

1楼liuweixuan昨天 14:14

好棒，不过目测空串的处理会有问题 :).

Re: hopeztm昨天 16:13

好像应该是 while 回复liuweixuan