アルゴリズムの二分ルックアップ
アルゴリズムの二分ルックアップ
思想
二分検索法の考え方は非常に簡単で、1つの秩序数列に対して、その中間の要素を探して、目標を探すかどうかを見て、そうでなければ、この検索目標が中間要素より小さいかどうかを見て、それから対応する区間内で上述の過程を繰り返します.
アルゴリズム#アルゴリズム#
いくつかの問題に注意する必要があります. whileサイクル:whileサイクルの条件はleftこれは、我々が設定した左右の境界から判断することができ、我々が設定したleft=0、right=n-1であるため、[left,right]は閉区間であり、left=rightの場合、[left,right]区間は同様に我々の設定を満たすため、このサイクル内はleft<=rightであるべきである. targetとarr[mid]の判断:target>arr[mid]の場合、left=midかleft=mid+1か. これはwhileにおける判断と1つの考え方であり、target>arr[mid]の場合、targetは[mid,r]ではなく[mid+1,r]にあり、midがtargetに等しいことは明らかではないため、targetとarr[mid]を比較する必要はない. も同様にtarget サイクル不変量:leftとrightの定義は非常に重要です.後でこの定義を絶えず維持しなければならないので、[left,right]という区間でtargetを探すことを保証しなければなりません.これはサイクル不変量です.leftとrightの値はずっと変化していますが、[left,right]に声明があります.区間内でtargetを探すのは永遠に変わらない.私たちがこのサイクルの不変量を維持すれば、私たちのアルゴリズムが正しいことを保証することができる.もちろん、ここではleft=0、right=n、すなわち[left,right]と定義することもできます.それに応じて、whileではこの定義を維持するために、left
leftもrightもintなので、値が十分大きい場合、mid=(left+right)/2を計算すると整数オーバーフローが発生する可能性があります!
そこで,この問題を回避するために減算法を用いて計算した.
完全に正しい二分ルックアップ
Utilを書いてテストの例を生成することができます
ArrayUtil.java
思想
二分検索法の考え方は非常に簡単で、1つの秩序数列に対して、その中間の要素を探して、目標を探すかどうかを見て、そうでなければ、この検索目標が中間要素より小さいかどうかを見て、それから対応する区間内で上述の過程を繰り返します.
アルゴリズム#アルゴリズム#
いくつかの問題に注意する必要があります.
private int binarySearch(T arr[], int n, T target) {
int left = 0, right = n - 1; // [left, right] target
while (left <= right) { // left = right ， [left, right]
int mid = (left + right) / 2;
if (arr[mid] == target)
return mid;
if (target > arr[mid])
left = mid + 1; // target [mid+1, r]
else
right = mid - 1; // target [left, mid - 1]
}
return -1;
}leftもrightもintなので、値が十分大きい場合、mid=(left+right)/2を計算すると整数オーバーフローが発生する可能性があります!
そこで,この問題を回避するために減算法を用いて計算した.
完全に正しい二分ルックアップ
public int binarySearch(T[] arr, int n, T target) {
int left = 0, right = n - 1; // [left, right] target
while (left <= right) { // left = right ， [left, right]
int mid = left + (right - left) / 2;
if (arr[mid].compareTo(target) == 0)
return mid;
if (target.compareTo(arr[mid]) > 0)
left = mid + 1; // target [mid+1, r]
else
right = mid - 1; // target [left, mid - 1]
}
return -1;
}Utilを書いてテストの例を生成することができます
ArrayUtil.java
public static Integer[] generateSortedArray(int n) {
assert n > 0;
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
arr[i] = i;
}
return arr;
} public static void main(String[] args) {
BinarySearch bs = new BinarySearch();
int n = (int)Math.pow(10, 7); // 10,000,000
Integer[] data = ArrayUtil.generateSortedArray(n);
long startTime = System.currentTimeMillis();
for (int i = 0; i < n; i++)
if (i != bs.binarySearch(data, n, i))
throw new IllegalStateException("find i failed");
long endTime = System.currentTimeMillis();
System.out.println("Binary Search success!");
System.out.println("Time cost: " + (endTime - startTime) + "ms");
}