이진 검색은 절반 검색이라고도 합니다. 이진 검색의 기본 아이디어는 사전에 있는 요소가 작은 것부터 큰 것까지 순서대로 배열(array)에 저장되어 있다고 가정하는 것입니다. > 먼저, 고정된 값 키를 사전의 중간 위치에 있는 요소의 키와 비교합니다. 동일하면 검색에 성공합니다.
그렇지 않으면 키가 작으면 바이너리입니다. 검색은 사전의 전반부에서 계속됩니다.
키가 크면 사전의 후반부에서 이진 검색을 계속합니다.
이런 방식으로 한 번의 비교 후에 검색 간격이 절반으로 줄어들고 검색이 성공하거나 실패할 때까지 계속됩니다.
짝수의 중간 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)); } }
더 보기 다중 알고리즘 이등분법에 대한 관련 기사를 찾으려면 PHP 중국어 웹사이트를 주목하세요!