이진 검색 방법에 대한 Java 알고리즘 예제 설명

이 글은 자바 알고리즘의 이진 검색 방법에 대한 자세한 설명을 중심으로 관련 정보를 소개합니다. 이 부분의 내용을 배우고 이해하는 데 도움이 되는 간단한 예를 소개합니다. 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!