二分探索は半探索とも呼ばれます。二分探索の基本的な考え方は、辞書内の要素が小さいものから大きいものへと順番に配列(配列)に格納されていると仮定することです。キーと辞書の中央の値が同じ位置にある要素のキーを比較します。等しければ、検索は成功します。そうでない場合は、辞書の前半で二分探索を続けます。 ;
キーが大きい場合は、辞書の後半を検索します。 で二分探索を続けます。
このようにして、1 回の比較の後、検索間隔は半分に短縮され、これは検索が成功するか失敗するまで続きます。
偶数の中から真ん中の 2 つの要素のいずれかを真ん中の要素として取得します
バイナリ検索はより効率的な検索方法であり、シーケンス テーブル内のキーによって辞書をソートする必要があります。
Java コード
正常にその場所に戻り、失敗した場合は負の数を返します
package ForTest; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Arithmetic{ public static<T extends Comparable<? super T> > int BinarySearch(List<T> array, int start, int end, T key) { int low; int high; int guess; if(array == null || start>end || start > array.size()-1 || end < 0) { return -1; } start = start < 0 ? 0 : start; low = start-1; end = end > array.size()-1 ? array.size()-1 : end; high = end+1; while (high - low > 1) { guess = ((high - low)>>1) + low; if (array.get(guess).compareTo(key) < 0) low = guess; else high = guess; } if (high == end +1 ) { return ~(end +1 ); } else if (array.get(high).compareTo(key) == 0) { return high; } else { return ~high; } } public static<T extends Comparable<? super T> > int BinarySearch(T[] array, int start, int end, T key) { List<T> stooges = Arrays.asList(array); return Arithmetic.BinarySearch(stooges, start, end, key); } public static void main(String[] args) { // TODO Auto-generated method stub ArrayList<Integer> a = new ArrayList<Integer>(); Float[] b = new Float[100]; for(int i=0; i<100; i++) { a.add(i); b[i] = (float) i; } System.out.println(""+Arithmetic.BinarySearch(a,0,1000,200)); System.out.println(""+Arithmetic.BinarySearch(b,0,100,2.f)); } }