如果我有一個數字列表,其中數字增加到一個點,然後在該點之後減少,是否有有限數量的猜測,與我將不得不做的集合的大小無關爲了找到最大值?查找集合中的最大值
值之間的距離是任意的,增加端的值的數量可以不同於減少端的值的數量。
什麼是最好的方法?檢查元素1,然後是最後一個元素,然後是兩者之間的一半?並重復?還是更復雜的東西?
這種算法的處理時間是多少?
如果我有一個數字列表,其中數字增加到一個點,然後在該點之後減少,是否有有限數量的猜測,與我將不得不做的集合的大小無關爲了找到最大值?查找集合中的最大值
值之間的距離是任意的,增加端的值的數量可以不同於減少端的值的數量。
什麼是最好的方法?檢查元素1,然後是最後一個元素,然後是兩者之間的一半?並重復?還是更復雜的東西?
這種算法的處理時間是多少?
您可以使用二進制搜索比較兩個相鄰元素而不是一個元素的固定值。從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)。它會比普通的二進制搜索稍慢,因爲您需要更多的比較。
根據列表中元素的數量,您可以嘗試類似於有序搜索的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
是返回包括在給定的索引之間的原始列表中的元素的列表的功能。