二分查找問題是比較經(jīng)典而且面試中?？嫉膯栴}，實現(xiàn)起來還是容易出問題，能夠過關(guān)的不多，請問實現(xiàn)一個二分查找有哪些容易錯的地方（比如小數(shù)的處理、數(shù)據(jù)相加的范圍等）？變種一：（多個公司的面試都喜歡出）如果有序序列發(fā)生偏移即把序列的后面一部分截取放在前面，比如：11 13 1 2 4 7 9此時再給定一個數(shù)，查找其在序列中是否存在（返回其位置），請問如何實現(xiàn)？變種二：同上題描述，找出序列中最小元素位置。變種三：給定任意一個序列，找出其中的一個谷/峰，谷的定義為兩邊的數(shù)均大于某個數(shù)。
3 回答
ibeautiful
TA貢獻(xiàn)1993條經(jīng)驗 獲得超6個贊
對于輸入的所有單詞，使用排序算法使得所有單詞按照字典序排列，然后用BS算法找到給定的單詞的下標(biāo)。
在給定的字符串序列中（按照字典序排列好的）存在一些空串，請你找出給定字符串的位置，不在里面返回 -1.
在一個排序好的數(shù)組中，有一些元素是重復(fù)的。 我們寫一個函數(shù)，對給定的數(shù)，我們返回這個數(shù)出現(xiàn)的次數(shù)。
在行列排序的矩陣中里面需找某個元素，例如如下輸入：
1 5 7 10
2 6 8 15
4 9 11 16
12 13 19 21
輸入滿足按行來看，是遞增排序，按列也是遞增排序，現(xiàn)在要是否存在某個元素。
慕斯709654
TA貢獻(xiàn)1840條經(jīng)驗 獲得超5個贊
說下第三個
要用三分法
記 l , m , r 分別為左端點、中端點、右端點。f(x) 為在x點的函數(shù)的值
取 lm = (l + m ） / 2 , rm = (m + r) / 2 ;
然后 比較 f(lm) f(rm)的關(guān)系 ， 相應(yīng)的更新l , m , r 就可以了
呼如林
TA貢獻(xiàn)1798條經(jīng)驗 獲得超3個贊
個人總結(jié)的幾個變種（只是為了描述算法本身，為了簡單不考慮越界等等異常情況），歡迎補充。
/*
二分查找的前提是數(shù)組有序
二分查找的時間復(fù)雜度：O（lgn）
以下列出二分查找的三種動機：
1、查找滿足條件的關(guān)鍵字的位置
2、查找滿足條件的最小位置
3、查找滿足條件的最大位置
找不到返回-1,找到了則返回位置
*///動機1(原始模型)：查找滿足條件的關(guān)鍵字的位置int BinarySearch(int *a,int l,int r){ int m; while(l<=r)
{
m=(l+r)/2; if(a[m]==key)
return m; if(a[m]>key)
r=m-1; else
l=m+1;
}
return-1;
}//動機2：找滿足條件的最小位置int BinarySearch(int *a,int l,int r){ int m,ans=-1; while(l<=r)
{
m=(l+r)/2; //滿足條件
if(ok())
ans=m,r=m-1; else
l=m+1;
}
return ans;
}//動機3：找滿足條件的最大位置int BinarySearch(int *a,int l,int r){ int m,ans=-1; while(l<=r)
{
m=(l+r)/2; //滿足條件
if(ok())
ans=m,l=m+1; else
r=m-1;
}
return ans;
}//動機2、3十分相似,舉一種常用情況：找小于等于某數(shù)的最大位置int BinarySearch(int *a,int l,int r,int key){ int m,ans=-1; while(l<=r)
{
m=(l+r)/2; if(key>=a[m])
ans=m,l=m+1; else
r=m-1;
}
return ans;
}//變型1：找滿足條件的最小數(shù)(double)double BinarySearch(double l,double r){
double m,ans; //保留n位小數(shù)就讓精度為n+1位,比如要求保留3位小數(shù)就讓精度為4位
while(r-l>=0.0001)
{
m=(l+r)*0.5; if(ok())
ans=m,r=m; else
l=m;
}
return ans;
}添加回答
舉報
0/150
提交
取消