一般情况下, 面试时常会问一种排序算法,
通常一般人会写出冒泡排序法, 稍高要求一点是写出二分查找
int
compare(int x, int y) {
return
(x > y ? 1 : (x == y ? 0 : -1));
}
int
binary_search(int list[], int nFind, int nLeft, int nRight) {
int
nMiddle = 0;
if
(nLeft <= nRight) {
nMiddle
= (nLeft + nRight)/2;
switch
(compare(list[nMiddle], nFind)) {
case
0:
{ return
nMiddle;}
break;
case
-1:
{return
binary_search(list, nFind, nMiddle+1, nRight);}
break;
case
1:
{return
binary_search(list, nFind, nLeft, nMiddle-1);}
break;
}
}
return
-1;
}
//
注:其中的nMiddle
= (nLeft + nRight)/2;
其实是可能会有溢出风险的,如果nLeft+nRight超过了该类型的最大值,就会发生溢出问题。
//
所以应该改成nMiddle = nLeft + (nRight - nLeft)/2