자바에서 이진 검색 알고리즘을 작성하는 방법
컴퓨터는 사람처럼 항목을 검색하지 않습니다. 인간은 무언가를 찾는 접근 방식을 변경할 수 있지만 컴퓨터는 특정 항목을 찾는 방법에 대한 구체적인 지침을 받아야 합니다. 바로 여기에서 표준 알고리즘이 유용합니다.
이진 검색은 표준 알고리즘의 한 예입니다. 정렬된 항목 배열에서 요소를 찾는 데 사용됩니다. 이 가이드에서는 바이너리 검색이 무엇인지, 어떻게 작동하는지, 자바에서 어떻게 구현할 수 있는지에 대해 이야기할 것입니다. 이진 검색의 두 가지 예를 살펴보겠습니다. 하나는 재귀적 접근 방식을 사용하고 다른 하나는 반복적 접근 방식을 사용합니다.
시작하겠습니다!
이진 검색이란 무엇입니까?
이진 검색은 정렬된 배열에서 요소의 위치를 찾는 검색 알고리즘입니다.
이진 검색은 목록을 반으로 나누는 것으로 시작됩니다. 그런 다음 검색은 알고리즘이 검색하는 번호와 중간 번호를 비교합니다.
숫자가 중간 숫자보다 작으면 목록의 아래쪽 절반에 대해 이 프로세스가 반복됩니다. 그렇지 않으면 이 프로세스가 목록의 위쪽 절반에 대해 반복됩니다.
이진 검색은 또 다른 일반적인 검색 유형인 선형 검색보다 더 효율적입니다. 알고리즘이 항목을 찾을 때마다 검색할 항목 수가 2배로 줄어들기 때문입니다.
이진 검색은 정렬된 항목 목록에서만 실행할 수 있습니다. 즉, 정렬된 목록이 아직 없는 경우 이진 검색을 실행하기 전에 정렬 알고리즘을 사용하여 정렬해야 합니다.
참가자의 81%는 부트캠프에 참석한 후 기술 직업 전망에 대해 더 자신감을 느꼈다고 말했습니다. 지금 부트캠프에 참여하십시오.
부트캠프 졸업생은 부트캠프 시작부터 첫 직장을 찾는 데까지 6개월도 채 걸리지 않았습니다.
이진 검색은 어떻게 작동합니까?
이진 검색은 반복 또는 재귀의 두 가지 방법으로 구현할 수 있습니다.
반복 이진 검색은 루프를 사용하여 목록에서 항목을 검색하는 것입니다. 재귀 이진 검색은 목록에서 항목을 찾기 위해 자신을 계속해서 호출하는 함수를 사용합니다. 재귀적 이진 검색은 분할 정복 접근 방식을 사용하여 항목을 찾습니다.
Java 재귀 가이드에서 재귀에 대해 자세히 알아볼 수 있습니다.
이진 검색을 구현하기 위한 일반적인 알고리즘은 사용하기로 결정한 접근 방식에 관계없이 동일합니다.
다음 목록을 고려하십시오.
| 6 | 7 | 8 | 9 | 10 |
우리는 목록에서 숫자 7을 검색할 것입니다. 시작하려면 목록에서 가장 낮은 위치와 가장 높은 위치를 나타내는 두 개의 포인터를 설정합니다.
| 낮음 | | | | 높음 |
| 6 | 7 | 8 | 9 | 10 |
다음으로 배열에서 중간 요소를 찾아야 합니다. (낮음 + 높음) / 2 공식을 사용하여 이를 수행할 수 있습니다. 이 경우 중간 요소는 8입니다.
우리의 알고리즘은 중간 요소가 우리가 검색하는 요소와 같은지 여부를 비교할 것입니다. 숫자가 같으면 검색이 중지될 수 있습니다. 8과 같지 않은 숫자 7을 찾고 있으므로 검색이 계속됩니다.
우리의 알고리즘은 우리가 찾고 있는 숫자가 중간 숫자보다 큰지 비교합니다. 더 크면 목록의 상단 절반에서 검색이 다시 시작됩니다. 이것은 low를 low =middle_number + 1과 같게 설정함으로써 수행됩니다. 그렇지 않으면 검색은 목록의 아래쪽 절반에서 다시 시작됩니다.
7(우리가 찾고 있는 숫자)은 8(가운데 숫자)보다 크지 않습니다. 이것은 우리 알고리즘이 목록의 아래쪽 절반을 검색한다는 것을 의미합니다. "high" 값을 high =middle_number – 1로 설정하여 이를 수행합니다.
| 낮음 | 중간 | 높음 | | |
| 6 | 7 | 8 | 9 | 10 |
이제 알고리즘이 검색을 반복할 것입니다. 중간 숫자 7을 우리가 찾고 있는 숫자와 비교할 것입니다. 숫자 7을 찾고 있으므로 검색 알고리즘이 중지됩니다. 목록에서 7의 위치를 찾았습니다!
자바 이진 검색을 구현하는 방법
이론은 끝났으므로 이제 검색을 구현하는 일만 남았습니다. 우리 스스로 목록을 검색하고 검색하는 것입니다. 우리를 검색하는 알고리즘을 코딩하는 것은 완전히 다른 문제입니다.
반복 방법을 사용하여 Java 바이너리 검색을 구현하는 프로그램을 작성하는 것으로 시작하겠습니다.
반복적 방법
searchItems라는 함수를 정의합시다. , 항목 목록을 검색합니다.
class BinarySearch {
int searchItems(int array[], int searchingFor, int low, int high) {
while (low <= high) {
int middle = low + (high - low) / 2;
if (array[middle] == searchingFor) {
return middle;
} else if (array[middle] < searchingFor) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return -1;
}
}
이 기능은 이진 검색을 사용하여 항목 목록을 검색합니다.
우리의 함수는 4개의 매개변수를 받습니다:검색하려는 목록(배열), 검색할 항목(searchingFor), 낮은 숫자(낮음), 높은 숫자(높음).
함수 내에서 while 루프를 선언했습니다. "low" 값이 "high"보다 작거나 같은 동안 루프가 실행됩니다.
while 루프는 중간 숫자를 계산하는 것으로 시작합니다. 그런 다음 해당 위치의 값이 검색하는 값과 같은지 확인합니다.
해당 숫자가 같으면 해당 값이 주 프로그램으로 반환됩니다. 그렇지 않은 경우 프로그램은 중간 위치의 값이 검색하는 값보다 작은지 확인합니다. 그렇다면 새로운 낮은 값이 설정됩니다.
그렇지 않으면 새로운 높은 값이 설정되어 목록이 목록의 위쪽 절반에서 다시 검색할 수 있습니다.
항목을 찾을 수 없으면 -1이 반환됩니다. 이것을 사용하여 1분 안에 목록 항목을 찾을 수 없다는 것을 주 프로그램에 알릴 것입니다.
메인 프로그램을 작성하지 않았기 때문에 코드는 아직 아무 것도 하지 않습니다. searchItems() 아래에 다음 코드를 추가합니다. BinarySearch 클래스의 함수:
public static void main(String args[]) {
BinarySearch newSearch = new BinarySearch();
int listToSearch[] = { 6, 7, 8, 9, 10 };
int listLength = listToSearch.length;
int numberToFind = 7;
int findNumber = newSearch.searchItems(listToSearch, numberToFind, 0, listLength - 1);
if (findNumber != -1) {
System.out.println(numberToFind + " was found at index position " + findNumber + ".");
} else {
System.out.println(numberToFind + " was not found in the list.");
}
} 코드를 실행하고 어떤 일이 일어나는지 봅시다:
7 was found at index position 1. We've found the position of our number!
우리의 메인 프로그램은 BinarySearch 클래스의 인스턴스를 초기화하는 것으로 시작합니다. 우리는 이것을 사용하여 프로그램에서 검색을 시작합니다. 그런 다음 세 가지 변수를 정의합니다.
- listToSearch:검색하려는 목록입니다.
- listLength:목록의 길이입니다.
- numberToFind:목록에서 찾고 있는 번호입니다.
이러한 변수를 정의한 후에는 searchItems()를 사용합니다. 목록에서 숫자를 찾기 위해 앞에서 선언한 함수입니다. 이 함수가 반환하는 값을 "findNumber" 변수에 할당합니다.
findNumber가 -1이 아닌 경우(즉, 번호가 발견되었음을 의미함) 검색 중인 항목의 인덱스 위치가 콘솔에 인쇄됩니다. 그렇지 않으면 번호를 찾을 수 없다는 메시지가 콘솔에 인쇄됩니다.
재귀적 방법
이진 검색을 구현하기 위해 재귀적 접근 방식을 취할 수 있습니다. 여기에서 지정된 항목을 찾을 때까지 자신을 호출하는 함수를 작성합니다.
이진 검색을 재귀적으로 수행하는 함수를 정의하여 시작하겠습니다.
class BinarySearch {
int searchItems(int array[], int searchingFor, int low, int high) {
if (high >= low) {
int middle = low + (high - low) / 2;
if (array[middle] == searchingFor) {
return middle;
} else if (array[middle] < searchingFor) {
searchItems(array, searchingFor, middle + 1, high);
} else {
searchItems(array, searchingFor, low, middle - 1);
}
}
return -1;
}
}
이 함수는 다른 방식으로 이진 검색을 구현합니다. while 루프를 사용하는 대신 if를 사용합니다. 높은 숫자가 낮은 숫자보다 같거나 작은지 확인하는 문.
이 문이 true로 평가되면 검색이 시작됩니다. 그렇지 않으면 -1이 반환되어 프로그램에 지정된 항목을 목록에서 찾을 수 없음을 알려줍니다.
if 내부 문에서 중간 숫자의 값이 우리가 찾고 있는 값과 같은지 확인합니다. 그렇다면 해당 번호를 주 프로그램으로 반환합니다.
이 문장이 참으로 평가되지 않으면 우리 프로그램은 중간 위치에 있는 숫자가 우리가 찾고 있는 숫자보다 작은지 확인합니다. 그렇다면 searchItems() 메서드가 다시 실행되지만 이번에는 낮은 숫자가 중간 숫자보다 큰 숫자가 됩니다. 이렇게 하면 목록에서 검색해야 하는 항목 수를 2로 나눕니다.
그렇지 않으면 searchItems() 다시 실행되고 가장 높은 숫자의 값은 중간 숫자에서 1을 뺀 값과 같게 됩니다. 이것은 목록의 왼쪽 절반까지만 검색을 구체화할 수 있음을 의미합니다.
이전에 작성한 것과 동일한 기본 기능을 사용하여 코드를 테스트할 수 있습니다. 코드를 실행할 때 어떤 일이 발생하는지 봅시다:
7 was found at index position 1.
우리 아이템을 다시 찾았습니다! 이번에는 반복적인 방법 대신 재귀적인 방법을 사용하여 숫자를 찾았습니다.
복잡성 분석
이진 탐색 알고리즘은 O(1)의 최상의 경우 복잡도를 갖습니다. 이것은 알고리즘에 의해 비교되는 첫 번째 항목이 검색되는 항목일 때 발생합니다.
이진 검색 알고리즘은 평균 및 최악의 경우 복잡도가 O(log n)입니다. 즉, 대부분의 경우와 최악의 경우 목록에서 검색해야 하는 항목 수에 따라 알고리즘 속도가 대수적으로 느려집니다.
결론
이진 검색은 정렬된 목록에서 요소의 위치를 찾는 데 사용됩니다. 이진 검색은 배열 부분의 중간에 있는 항목을 알고리즘이 검색하는 번호와 비교합니다.
이진 검색은 선형 검색보다 더 효율적입니다. 검색을 수행할 때마다 검색해야 하는 값의 수를 2로 나누기 때문입니다.
이제 전문 프로그래머처럼 Java에서 바이너리 검색을 구현할 준비가 되었습니다.