無限式查找-----2013年2月28日

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

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

      1.最開始,二分查找x[0]和x[1]，即查找區域為[0,1)這個左閉右開區間，區間的大小是。此時start=0,end=1。這是認為構造的一個适合二分查找法的區間。

      2.如果在之前沒有查找到，把start=end,end+=。此時的區間大小是。再進行二分查找。如果還沒找到，繼續增大區間到,直到找到或到達最大值MAX。

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

本文轉自NeilHappy 51CTO部落格，原文連結：http://blog.51cto.com/neilhappy/1142075，如需轉載請自行聯系原作者