ローテーションされたソート済みリストがあり、そのリストでバイナリ検索を実行して最小要素を見つけたいと考えています。
最初のリストが{1,2,3,4,5,6,7,8}であると仮定しましょう。ローテーションされたリストは{5,6,7,8,1,2,3,4}のようになります
この場合、通常の二分探索は機能しません。これを行う方法についてのアイデア。
- 編集
私は別の条件を持っています。リストがソートされていない場合はどうなりますか??
12644 次
11 に答える
29
二分探索アルゴリズムを少し変更するだけで十分です。完全に実行可能な Java のソリューションを次に示します ( Delphi の実装についてはSergの回答を、アルゴリズムの視覚的な説明についてはtkr の回答を参照してください)。
import java.util.*;
public class BinarySearch {
static int findMinimum(Integer[] arr) {
int low = 0;
int high = arr.length - 1;
while (arr[low] > arr[high]) {
int mid = (low + high) >>> 1;
if (arr[mid] > arr[high]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public static void main(String[] args) {
Integer[] arr = { 1, 2, 3, 4, 5, 6, 7 };
// must be in sorted order, allowing rotation, and contain no duplicates
for (int i = 0; i < arr.length; i++) {
System.out.print(Arrays.toString(arr));
int minIndex = findMinimum(arr);
System.out.println(" Min is " + arr[minIndex] + " at " + minIndex);
Collections.rotate(Arrays.asList(arr), 1);
}
}
}
これは以下を出力します:
[1, 2, 3, 4, 5, 6, 7] Min is 1 at 0
[7, 1, 2, 3, 4, 5, 6] Min is 1 at 1
[6, 7, 1, 2, 3, 4, 5] Min is 1 at 2
[5, 6, 7, 1, 2, 3, 4] Min is 1 at 3
[4, 5, 6, 7, 1, 2, 3] Min is 1 at 4
[3, 4, 5, 6, 7, 1, 2] Min is 1 at 5
[2, 3, 4, 5, 6, 7, 1] Min is 1 at 6
こちらもご覧ください
- 配列を使用した Java Collections.rotate() が機能しない
Integer[]代わりに理由を説明しますint[]
- Google Research ブログ: ほぼすべてのバイナリ検索とマージソートが壊れている
>>> 1代わりに理由を説明します/ 2
重複について
重複すると、 でこれを行うことができなくなることに注意してくださいO(log N)。1多くの と 1 つ0ので構成される次のビット配列を考えてみましょう。
(sorted)
01111111111111111111111111111111111111111111111111111111111111111
^
(rotated)
11111111111111111111111111111111111111111111101111111111111111111
^
(rotated)
11111111111111101111111111111111111111111111111111111111111111111
^
この配列はさまざまな方法で回転できますが、「中央」の左側にあるか右側にあるかを判断する方法がないため、インNを見つけることは不可能です。0O(log N)
私は別の条件を持っています。リストがソートされていない場合はどうなりますか??
次に、最初に並べ替えてそこから続行する場合を除き、最小値を見つけるために線形検索を行う必要があります。
こちらもご覧ください
于 2010-05-09T03:26:01.463 に答える
10
推奨されるアルゴリズムを説明するための図を次に示します。
于 2010-05-09T09:27:43.470 に答える
3
[1, end) の範囲で二分法を実行するだけです。list - list[end]二分法は、符号の変化を検索することによって関数内のゼロを探し、O(log n) で動作します。
例えば、
{5,6,7,8,1,2,3,4} -> {1,2,3,4,-3,-2,-1,0}
次に、そのリスト {1,2,3,4,-3,-2,-1} に対して (離散化された) 二分法を使用します。回転ポイントに対応する 4 と -3 の間のゼロクロッシングが見つかります。
于 2010-05-09T04:02:39.947 に答える
3
そのリストでバイナリ検索を実行して、最小要素を見つけたいと思います。
三項探索は、次のような場合に機能します: 関数が局所的最小値を 1 つだけ持つ場合。
http://en.wikipedia.org/wiki/Ternary_search
編集 二度目の読書で、私はおそらく質問を誤解しました:関数は三分探索の要件に準拠していません:/しかし、二分探索は機能しませんか? 元の順序が増加していたとします。
if (f(left) < f(middle))
// which means, 'left' and 'middle' are on the same segment (before or after point X we search)
// and also 'left' is before X by definition
// so, X must be to the right from 'middle'
left = middle
else
right = middle
于 2010-05-09T02:52:25.553 に答える
2
[i,j]list の一部のサブシーケンスを選択します[first, last)。[i,j]不連続性を含まない場合 ( の場合*i <= *j)、または含む場合 (残りの要素(j, last) U [first, i)が適切にソートされる場合) のいずれかです*j <= *i。
1 つの要素に絞り込むまで、疑わしい範囲を再帰的に 2 分割します。O(log N) 回の比較を行います。
于 2010-05-09T03:28:24.333 に答える
2
Delphi バージョン - 3 番目に改善された (polygenelubricants コードのおかげで - もう 1 つの比較が削除されました) バリアント:
type
TIntegerArray = array of Integer;
function MinSearch(A: TIntegerArray): Integer;
var
I, L, H: Integer;
begin
L:= Low(A); // = 0
H:= High(A); // = Length(A) - 1
while A[L] > A[H] do begin
I:= (L + H) div 2; // or (L + H) shr 1 to optimize
Assert(I < H);
if (A[I] > A[H])
then L:= I + 1
else H:= I;
end;
Result:= A[L];
end;
于 2010-05-09T03:40:24.227 に答える
2
コードの単純さと可読性を維持したい場合、再帰は非常に優れています。しかし、再帰のコストが大きく、実際にはスケーラブルではないため、再帰を回避して可読性を維持できる場合は、そのほうがよいでしょう。
これは、上記で説明したのとほぼ同じロジックを使用した単純な反復方法です (バイナリ検索を利用して、小さなパーティション ロジックを追加しています)。
private static int partitionSearch(int[] sortedArray, int numToFind) {
if(sortedArray[0] > numToFind && sortedArray[sortedArray.length -1 ] < numToFind)
return -1;
boolean isInFirstPartition = sortedArray[0] <= numToFind;
int startIndex = 0;
int endIndex = sortedArray.length -1;
int currentIndex;
int currentValue;
if(isInFirstPartition) {
do {
currentIndex = (startIndex + endIndex) / 2;
currentValue = sortedArray[currentIndex];
if(currentValue == numToFind)
return currentIndex;
if(currentValue > sortedArray[startIndex] && sortedArray[currentIndex] < numToFind)
startIndex = currentIndex + 1;
else
endIndex = currentIndex - 1;
} while (startIndex <= endIndex);
} else {
do {
currentIndex = (startIndex + endIndex) / 2;
currentValue = sortedArray[currentIndex];
if(currentValue == numToFind)
return currentIndex;
if(currentValue < sortedArray[endIndex] && sortedArray[currentIndex] > numToFind)
endIndex = currentIndex - 1;
else
startIndex = currentIndex + 1;
} while (startIndex <= endIndex);
}
return -1;
}
于 2012-09-30T19:55:18.233 に答える
2
C++ 11 では、この問題はpartition_pointで解決できます。
std::vector<int> arr = {5,6,7,8,1,2,3,4};
auto rotation_point = std::partition_point(arr.begin(), std::prev(arr.end()),
[&arr](int elem) { return elem > arr.back(); });
于 2016-03-25T20:23:34.493 に答える
2
Javaでのバイナリ検索アルゴリズムの実装の私のバージョン:
/**
* Works only for arrays with NO duplicates.
* Work also for zero-shifted array, e.g fully sorted, when shift = 0.
*/
public static int searchInShiftedArr(int[] arr, int key) {
if (arr == null || arr.length == 0) {
return -1;
}
int low = 0;
int high = arr.length - 1;
int mid; // declared outside loop to avoid constant memory allocation for this variable
while (low <= high) {
mid = (low + high) >>> 1; // same as "(low + high) / 2", but avoid negative overflow and should be faster than "low + (high - low)/2"
if (arr[mid] == key) {
return mid;
}
if (arr[low] <= arr[mid]) { // means left half of the array is sorted
if (arr[low] <= key && key < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
} else { // means right half of the array is sorted
if (arr[mid] < key && key <= arr[high]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return -1;
}
コードは 5000 の TestCasesを正常に通過したので、本番環境の準備ができていると思います。
于 2015-01-03T15:42:04.610 に答える
2
C++ では、このコード ( O(log(n)) ) を使用して、ローテーションされたソート済みリストのローテーション数を取得できます。
findRotations(const vector<int> &A) {
int len = A.size(), low = 0, high = len - 1, result = -1, target = A[len-1];
while(low <= high){
int mid = low + (high-low)/2;
if(A[mid] > target){
low = mid + 1;
}
else{
result = mid;
high = mid - 1;
}
}
return result;
}
リストがソートされていない場合は、元の配列が何であったかを知っておく必要があり、回転点 ( O(n) ) を線形に確認できます。
于 2020-06-18T09:33:28.083 に答える
1
このようなものがうまくいくかもしれません（テストされていません）：
//assumes the list is a std::vector<int> myList
int FindMinFromRotated(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
if (begin == end)
throw std::invalid_argument("Iterator range is singular!");
if (std::distance(begin, end) == 1) //What's the min of one element?
return *begin;
if (*begin < *end) //List is sorted if this is true.
return *begin;
std::vector<int>::iterator middle(begin);
std::advance(middle, std::distance(begin, end)/2);
if (*middle < *begin) //If this is true, than the middle element selected is past the rotation point
return FindMinFromRotated(begin, middle)
else if (*middle > *begin) //If this is true, the the middle element selected is in front of the rotation point.
return FindMinFromRotated(middle, end)
else //Looks like we found what we need :)
return *begin;
}
于 2010-05-09T03:02:30.583 に答える