자바의 바이너리 검색 알고리즘

1. 개요

이 기사에서는 단순한 선형 검색에 비해 이진 검색의 장점을 다루고 Java에서 구현하는 방법을 살펴 봅니다.

2. 효율적인 검색의 필요성

우리가 와인 판매 사업을하고 있고 수백만 명의 구매자가 매일 우리의 애플리케이션을 방문한다고 가정 해 보겠습니다.

앱을 통해 고객은 가격이 n 달러 미만인 품목을 필터링 하고 검색 결과에서 병을 선택하여 카트에 추가 할 수 있습니다. 매초 가격 제한이있는 와인을 찾는 수백만 명의 사용자가 있습니다. 결과는 빨라야합니다.

백엔드에서 우리의 알고리즘은 고객이 입력 한 가격 제한을 목록에있는 모든 와인 병의 가격과 비교하여 전체 와인 목록에 대한 선형 검색을 실행합니다.

그런 다음 가격이 가격 한도 이하인 항목을 반환합니다. 이 선형 검색의 시간 복잡도는 O (n) 입니다.

즉, 시스템의 와인 병 수가 많을수록 더 많은 시간이 소요됩니다. 검색 시간은 도입 된 새 항목 수에 비례하여 증가합니다.

정렬 된 순서로 항목을 저장하고 이진 검색을 사용하여 항목을 검색하면 O (log n) 의 복잡성을 얻을 수 있습니다 .

이진 검색을 사용하면 검색 결과에 걸리는 시간이 데이터 세트의 크기에 따라 자연스럽게 증가하지만 비례하지는 않습니다.

3. 바이너리 검색

간단히 말해서 알고리즘은 값을 배열의 중간 요소와 비교합니다 . 같지 않으면 키가 속할 수없는 절반이 제거되고 성공할 때까지 나머지 절반에 대한 검색이 계속됩니다.

여기서 중요한 점은 배열이 이미 정렬되어 있다는 것입니다.

나머지 절반이 비어있는 상태로 검색이 끝나면 가 배열에없는 것입니다.

3.1. 반복적 Impl

public int runBinarySearchIteratively( int[] sortedArray, int key, int low, int high) { int index = Integer.MAX_VALUE; while (low <= high) { int mid = (low + high) / 2; if (sortedArray[mid]  key) { high = mid - 1; } else if (sortedArray[mid] == key) { index = mid; break; } } return index; }

runBinarySearchIteratively의 방법은 소요 sortedArray , 로우하이 의 인덱스 sortedArray 인수로한다. 이 방법은 처음으로 실행될 때 로우 의 첫 번째 인덱스 sortedArray는 그동안, 0 높이 의 마지막 인덱스 sortedArray는 1 - 길이와 동일하다.

중간 의 중간 인덱스 sortedArray . 이제 알고리즘은 sortedArray 중간 인덱스의 배열 값과 비교 하는 while 루프를 실행합니다 .

3.2. 재귀 Impl

이제 단순하고 재귀적인 구현도 살펴 보겠습니다.

public int runBinarySearchRecursively( int[] sortedArray, int key, int low, int high) { int middle = (low + high) / 2; if (high < low) { return -1; } if (key == sortedArray[middle]) { return middle; } else if (key < sortedArray[middle]) { return runBinarySearchRecursively( sortedArray, key, low, middle - 1); } else { return runBinarySearchRecursively( sortedArray, key, middle + 1, high); } } 

runBinarySearchRecursively의 방법은 받아 sortedArray , 키, 의 인덱스 sortedArray을 .

3.3. 어레이 사용 . binarySearch ()

int index = Arrays.binarySearch(sortedArray, key); 

정수 배열에서 검색 할 sortedArrayint 는 Java Arrays 클래스 의 binarySearch 메소드에 인수로 전달됩니다 .

3.4. 컬렉션 사용 . binarySearch ()

int index = Collections.binarySearch(sortedList, key); 

Integer 객체 목록에서 검색 할 sortedListInteger 는 Java Collections 클래스 의 binarySearch 메서드에 인수로 전달됩니다 .

3.5. 공연

알고리즘을 작성하기 위해 재귀 적 또는 반복적 접근 방식을 사용할지 여부는 대부분 개인 취향의 문제입니다. 그러나 여전히 우리가 알아야 할 몇 가지 사항이 있습니다.

1. 스택 을 유지하는 오버 헤드로 인해 재귀가 느려질 수 있으며 일반적으로 더 많은 메모리를 차지합니다.

2. 재귀는 스택 친화적 이지 않습니다 . 빅 데이터 세트를 처리 할 때 StackOverflowException 이 발생할 수 있습니다.

3. 재귀는 반복적 인 접근 방식에 비해 코드를 더 짧게 만들기 때문에 코드에 명확성을 추가합니다.

이상적으로 이진 검색은 n의 큰 값에 대한 선형 검색과 달리 비교 횟수가 적습니다. n 값이 작은 경우 선형 검색이 이진 검색보다 더 잘 수행 될 수 있습니다.

이 분석은 이론적이며 상황에 따라 달라질 수 있음을 알아야합니다.

또한 이진 검색 알고리즘에는 비용이 드는 정렬 된 데이터 세트가 필요합니다 . 데이터를 정렬하기 위해 병합 정렬 알고리즘을 사용하는 경우 n log n 의 추가 복잡성이 코드에 추가됩니다.

따라서 먼저 요구 사항을 잘 분석 한 다음 요구 사항에 가장 적합한 검색 알고리즘을 결정해야합니다.

4. 결론

이 튜토리얼은 이진 검색 알고리즘 구현과 선형 검색 대신 사용하는 것이 더 나은 시나리오를 보여주었습니다.

GitHub에서 튜토리얼 코드를 찾으십시오.