2012-11-19 154 views
0

如果我有一個數字列表,其中數字增加到一個點,然後在該點之後減少,是否有有限數量的猜測,與我將不得不做的集合的大小無關爲了找到最大值?查找集合中的最大值

值之間的距離是任意的,增加端的值的數量可以不同於減少端的值的數量。

什麼是最好的方法?檢查元素1,然後是最後一個元素,然後是兩者之間的一半?並重復?還是更復雜的東西?

這種算法的處理時間是多少?

回答

0

您可以使用二進制搜索比較兩個相鄰元素而不是一個元素的固定值。從a = 0開始,b:= n,i:=(a + b)/ 2,並將元素(i)與元素(i + 1)進行比較。如果你注意到e(i + 1)> e(i),你知道斷點在i之後,所以設置:= i。如果e(i)< e(i-1),則情況正好相反,並且您設置b:= i。

複雜性將會是O(log n)。它會比普通的二進制搜索稍慢,因爲您需要更多的比較。

0

根據列表中元素的數量,您可以嘗試類似於有序搜索的rcursive算法。

僞代碼:

List search(int index, List listpart){ 
    if(listpart.length()==1){ // already found 
     return listpart 
    } 
    else if(listpart(index+1)>listpart(i) && listpart(index-1)<listpart(i)){ //search right part 
     List listpart_tmp = getlistpart(listpart, index, listpart.length()) 
     return search(index+(listpart.length()/4), listpart_tmp 
    } 
    else if(listpart(index+1)<listpart(i) && listpart(index-1)>listpart(i)){ //search left part 
     List listpart_tmp = getlistpart(listpart, 0, index) 
     return search(index-(listpart.length()/4), listpart_tmp 
    } 
    else if(listpart(index+1)<listpart(i) && listpart(index-1)<listpart(i)){ //found 
     return getlistpart(listpart, index, index) 
    } 
} 

功能

getlistpart 

是返回包括在給定的索引之間的原始列表中的元素的列表的功能。