이 글은 자바 알고리즘의 이진 검색 방법에 대한 자세한 설명을 중심으로 관련 정보를 소개합니다. 이 부분의 내용을 배우고 이해하는 데 도움이 되는 간단한 예를 소개합니다. Java 알고리즘의 이진 검색 방법.
Principle
검색 범위가 정렬된 배열(예: 오름차순)이고 해당 요소가 이 배열에 있는 경우, 인덱스를 반환하고, 그렇지 않으면 -1이 반환됩니다. 배열의 길이를 통해 중간 요소의 인덱스를 추출할 수 있으며, 그 값은 목표 값과 비교됩니다. 중간 위치 값이 목표 값보다 작을 경우 오른쪽 부분부터 검색이 수행됩니다. 이진 검색 알고리즘이 빠른 이유는 배열의 모든 요소를 순회하는 것이 아니라, 요소 중 일부만 검색하여 대상을 찾거나 존재하지 않는다고 판단하기 때문입니다. 물론 검색이 전제입니다. 범위는 순서가 지정된 배열입니다.
Java의 간단한 구현
package me.geed.algorithms; public class BinarySearch { /** * 从一个有序数组(如升序)中找到值为key元素 * @param key * @param array * @return 如果找到目标元素,则返回其在数组中的索引,否则返回-1 */ public static int find(int key, int[] array){ int low = 0; int high = array.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (array[mid] > key) { high = mid - 1; } else if (array[mid] < key) { low = mid + 1; } else { return mid; } } return -1; } public static void main(String[] args) { // TODO Auto-generated method stub int[] array = {2, 3, 5, 9, 10, 13, 23, 45, 78, 89, 100, 128, 256}; System.out.println("目标元素索引值:" + BinarySearch.find(9, array)); System.out.println("目标元素索引值:" + BinarySearch.find(26, array)); } }
출력 결과는 다음과 같습니다.
目标元素索引值:3 目标元素索引值:-1
이진 검색 알고리즘의 시간 복잡도
범위 배열 길이가 N이고, 다음의 시간 복잡도는 이진 검색은 O(logN)
위 내용은 이진 검색 방법에 대한 Java 알고리즘 예제 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!