HOWTO · Java
Java 바이너리 검색 대화 형 및 재귀
이 튜토리얼은 바이너리 검색 알고리즘을 사용하는 방법을 보여줍니다.
이 페이지의 내용
노트
이진 검색에 대한 자세한 내용은 이진 검색 알고리즘 문서를 참조하세요.
반복 이진 검색 알고리즘
n요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정하고X요소를 찾으려고합니다.
-
lo를0으로,hi를n - 1로 설정합니다. -
lo<hi동안 :mid=lo + (hi - lo)/2를 설정합니다.A[mid] == X이면 요소가 indexmid를 반환하는 것을 발견했습니다.A[mid] < X이면 요소의 왼쪽 절반을 버리고lo를mid+1로 설정합니다.- 그렇지 않으면
A[mid] > X이면 요소의 오른쪽 절반을 버리고hi를mid-1로 설정합니다.
-
요소를 찾을 수 없으므로
-1을 반환합니다.
바이너리 검색을위한 Java 반복 프로그램
class BinarySearch {
int binarySearch(int arr[], int x) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
lo = mid + 1;
else
hi = mid - 1;
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {1, 2, 3, 4, 5};
int n = arr.length;
int x = 5;
int position = ob.binarySearch(arr, x);
if (position == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index: " + position);
}
}
출력:
Element found at index: 4
재귀 바이너리 검색 알고리즘
n요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정하고X요소를 찾으려고합니다.
-
lo를0으로,hi를n-1로 초기화합니다. -
lo>hi이면 배열 검색 공간을 모두 사용하고 -1을 반환합니다. -
중간 점
mid를lo+(hi-lo)/2로 계산합니다. 배열을0에서mid - 1까지의 요소가있는 아래쪽 절반과mid에서n - 1까지의 요소가있는 위쪽 절반으로 배열을 나눕니다. -
X==mid이면 대상 요소가mid를 반환하는 것을 발견했습니다. -
X가mid보다 작 으면binarysearch(arr, lo, mid-1)를 재귀 적으로 호출하여 배열의 아래쪽 절반을 검색합니다. -
그렇지 않으면
X가mid보다 크면binarysearch(arr, mid+1, hi)를 재귀 적으로 호출하여 배열의 위쪽 절반을 검색합니다.
바이너리 검색을위한 Java 재귀 프로그램
class BinarySearch {
int binarySearch(int arr[], int lo, int hi, int x) {
if (hi >= lo && lo < arr.length - 1) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, lo, mid - 1, x);
return binarySearch(arr, mid + 1, hi, x);
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {1, 2, 3, 4, 5};
int n = arr.length;
int x = 2;
int position = ob.binarySearch(arr, 0, n - 1, x);
if (position == -1)
System.out.println("Element not found !!!");
else
System.out.println("Element found at index: " + position);
}
}
출력:
Element found at index: 1
Arrays.binarySearch()개요
Java는Arrays.binarySearch()함수를 사용할 준비가되어 있으므로 함수를 직접 구현할 필요가 없습니다. 사용이 매우 간단하고 효율적으로 구현 된 방법이며 오류가 발생하지 않습니다.
통사론
public static int binarySearch(T arr, T key)
T는int, float, short, long, byte, char, double 및 사용자 정의Object 중 하나 일 수 있습니다.
구현 된 이진 검색과 마찬가지로 배열을 정렬해야합니다. 그렇지 않으면 결과가 정의되지 않습니다. binary search algorithm을 사용하여 배열을 검색하고 대상 요소의 인덱스를 찾습니다. 대상 요소가 여러 번 발생하면 그중 하나의 색인을 반환 할 수 있습니다.
매개 변수
Arr |
입력 배열 |
Key |
우리가 찾고있는 타겟 요소. |
반환
대상 요소를 찾으면 색인을 리턴합니다. 그렇지 않으면beg - 1을 리턴합니다. 여기서beg는 배열 검색 공간의 시작 색인입니다.
바이너리 검색을위한 Java 프로그램
import java.util.Arrays;
class BinarySearchExample {
public static void main(String args[]) {
int arr[] = {1, 2, 3, 4, 5};
int key = 2;
int result = Arrays.binarySearch(arr, key);
if (result < 0)
System.out.println("Element is not found!");
else
System.out.println("Element is found at index: " + result);
}
}
출력:
Element is found at index: 1
