자바의 BinarySearch()-java지도 시간-php.cn

자바의 BinarySearch()

WBOY

풀어 주다： 2024-08-30 16:12:22

원래의

970명이 탐색했습니다.

Java에서 BinarySearch()는 이진 검색 알고리즘을 사용하여 여러 요소 중에서 특정 핵심 요소를 검색하는 데 도움을 주는 메서드입니다. 이 작업을 수행하려면 요소를 오름차순으로 정렬해야 합니다. 정렬되지 않은 경우 Arrays.sort(arr) 메서드를 사용하여 정렬할 수 있습니다. 그렇지 않으면 결과가 정의되지 않은 것으로 간주됩니다. 선형 검색에 비해 이진 검색이 더 빠른 것으로 간주됩니다. 이로 인해 이진 검색의 시간 복잡도는 O(log n)이라고 합니다. 또한, BinarySearch() 메소드는 java.util.Arrays 패키지에서 인스턴스화될 수 있습니다. BinarySearch() 메서드에 대한 자세한 내용은 다음 섹션에서 설명합니다.

구문:

무료 소프트웨어 개발 과정 시작

웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등

public static int binarySearch(Object[] a, Object key)

로그인 후 복사

여기서, 매개변수 a와 key는 각각 검색해야 할 배열과 검색해야 할 값입니다.

binarySearch() 메서드는 검색한 핵심 요소의 인덱스를 반환합니다. 키 요소를 찾을 수 없는 경우 삽입되었을 키 요소가 있는 삽입 지점이 반환됩니다. 검색의 핵심 요소가 배열의 다른 요소와 비교할 수 없는 경우 ClassCastException이라는 예외가 발생합니다.

Java에서 BinarySearch() 메서드는 어떻게 작동하나요?

이 메소드가 Java에서 어떻게 작동하는지 살펴보겠습니다.

k가 검색해야 할 핵심 요소라고 가정해 보겠습니다. k를 배열의 중간 요소와 비교합니다.
k가 중간 위치에 있는 요소와 일치하는 경우 중간 인덱스를 반환해야 합니다.
그렇지 않고 k가 중간 위치의 요소보다 높으면 k는 중간 요소의 오른쪽에서만 찾을 수 있습니다.
그렇지 않으면 중간 요소의 왼쪽에서 찾을 수 있습니다.

Java에서 BinarySearch()를 구현하는 예

다음은 BinarySearch() 메서드에 대한 일부 프로그램의 예입니다.

예시 #1

코드:

import java.util.Arrays;
public class BinarySearchExample
{
public static void main(String[] args)
{
//create a byte array
byte ba[] = {05, 10, 15, 20, 25, 30};
//create a character array
char ca[] = {'a', 'n', 's', 'p', 'v', 'i', 'd'};
//create an integer array
int ia[] = { 10, 20, 15, 22, 35};
//create a double array
double da[] = {10.1 , 15.34 , 22.25, 13.5};
//create a float array
float fa[] = {13.2f, 25.1f , 22.2f , 43.5f };
//sort all the arrays that created above
Arrays.sort(ba);
Arrays.sort(ca);
Arrays.sort(ia);
Arrays.sort(da);
Arrays.sort(fa);
//enter the key elements that has to be searched in the array
byte bKey = 15;
char cKey = 'i';
int iKey = 22;
double dKey = 15.34;
float fKey = 22.2f;
System.out.println("Element "+ bKey + " is found at the position of " + Arrays.binarySearch(ba,bKey) );
System.out.println("Element "+ cKey + " is found at the position of " + Arrays.binarySearch(ca,cKey) );
System.out.println("Element "+ iKey + " is found at the position of " + Arrays.binarySearch(ia,iKey) );
System.out.println("Element "+ dKey + " is found at the position of " + Arrays.binarySearch(da,dKey) );
System.out.println("Element "+ fKey + " is found at the position of " + Arrays.binarySearch(fa,fKey) );
}
}

로그인 후 복사

출력:

자바의 BinarySearch()

위의 program.Sort() 메소드에서 Array를 사용하여 배열을 정렬한 후 문자, 정수, 부동 소수점, 더블, 바이트 등 다양한 유형의 특정 배열이 생성되고, 배열에서 검색해야 할 요소가 선언됩니다. 그런 다음 Arrays.binarySearch() 메서드를 사용하여 검색된 요소의 인덱스를 인쇄합니다.

배열에는 없는 핵심 요소가 주어졌다고 가정해 보겠습니다. 출력은 어떻게 될까요??

그것을 찾기 위해 핵심 요소의 코드를 아래와 같이 변경해 보겠습니다.

바이트 bKey = 15;
char cKey = 'i';
int iKey = 89;
이중 dKey = 15.34;
float fKey = 22.2f;

즉, iKey=89가 배열에 없으면 아래와 같이 출력됩니다.

자바의 BinarySearch()

보시다시피 위치는 -6으로 출력됩니다. 요소를 검색했는데 찾을 수 없는 경우 해당 요소가 있으면 인덱스의 음수 값이 반환되기 때문입니다. 즉, int ia[] = { 10, 20, 15, 22, 35} 는 주어진 배열입니다. 89가 존재한다면 배열은 int ia[] = { 10, 20, 15, 22, 35, 89};

인덱스가 6이었음을 분명히 알 수 있습니다. 원래 배열에는 없기 때문에 해당 특정 인덱스의 음수 값이 위 출력에 반환됩니다.

예시 #2

다음과 같이 재귀를 사용하여 이진 검색을 수행할 수도 있습니다.

코드:

//sample class
class BinarySearchExample{
public static int binarySearch(int a[], int f, int l, int k){
//if last element is greater than or equal to first element
if (l>=f)
{
//find the mid
int m = f + (l - f)/2;
//if the key element that is searching is found in middle position, return mid position
if (a[m] == k)
{
return m;
}
//if key element is less than element in middle position, search the left <u>subarray</u>
if (a[m] > k){
return binarySearch(a, f, m-1, k);
}
//if key element is greater than the element in middle position, search the right <u>subarray</u>
else{
return binarySearch(a, m+1, l, k);
}
}
return -1;
}
public static void main(String args[]){
//initialise the array
int a[] = {34,45,54,68,79};
int k = 68;
int l = a.length-1;
//store the position in variable res
int res = binarySearch(a,0,l,k);
if (res == -1)
System.out.println("Sorry!! Can't find the element....!");
else
System.out.println("Element is found at the position: "+res);
}
}

로그인 후 복사

출력:

자바의 BinarySearch()