? ? ? ?問題描述:已知一個數(shù)組x[]，元素個數(shù)有多少并不很清楚，但是數(shù)組元素已經(jīng)依順序從小到大排好，而且在數(shù)組最后添加了足夠多的MAX記號;MAX表示最大的值，比數(shù)組中每一個元素都大，而且個數(shù)足夠多。編寫一個程序，在這個數(shù)組中找出某個給定的值。

? ? ? 思路:二分查找法是一個非常高效的算法，但要想使用二分查找法，必須滿足2個條件:1.元素是有序的，可以從小到大排列，也可以從大到小排列。2.知道元素集合的上界和下界。本題中元素已經(jīng)從小到大排列，但是不知道數(shù)組的上界。所以，解法如下:

? ? ? 1.最開始,二分查找x[0]和x[1]，即查找區(qū)域為[0,1)這個左閉右開區(qū)間，區(qū)間的大小是。此時start=0,end=1。這是認(rèn)為構(gòu)造的一個適合二分查找法的區(qū)間。

? ? ? 2.如果在之前沒有查找到，把start=end,end+=。此時的區(qū)間大小是。再進(jìn)行二分查找。如果還沒找到，繼續(xù)增大區(qū)間到,直到找到或到達(dá)最大值MAX。

? ? ? 代碼很簡單，在此就不贅述了。

? ? ? 參考資料:《C語言精選名題百則技巧篇》

? ? ? 如果你覺得我的文章對你有幫助，請推薦一下，非常感謝!

轉(zhuǎn)載于:https://www.cnblogs.com/NeilHappy/archive/2013/02/28/2936467.html

總結(jié)

以上是生活随笔為你收集整理的无限式查找-----2013年2月28日的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。