이진 검색 알고리즘

이진 검색이란 무엇입니까?

이진 검색은 검색 문제를 해결하는 알고리즘이며 입력은 정렬된 요소 목록입니다. 찾고 있는 요소가 해당 목록에 있으면 해당 요소가 있는 위치를 반환합니다. 그렇지 않으면 이진 검색은 -1 또는 null을 반환합니다.

사전에서 문자 M으로 시작하는 단어를 검색한다고 가정합니다. 처음부터 시작하여 Ms에 도달할 때까지 페이지를 계속 넘길 수 있습니다. 그러나 Ms가 사전의 중앙 근처에 있을 것이라는 것을 알고 있기 때문에 중간 페이지에서 시작할 가능성이 더 큽니다. 일반적으로 n개의 목록에 대해 이진 검색은 최악의 경우 O(log n) 단계를 수행하는 반면 단순 검색은 n 단계를 수행합니다.

삽화가 있는 유사 코드

방법 이름:
이진 검색(a, x)

입력:
a: 검색할 정렬된 배열
x: 우리가 찾고 있는 값

예를 들어 int[]{11, 88, 99, 111, 223, 999, 1028}을 사용합니다.


출력:
a[i] == x 또는 찾을 수 없는 경우 -1인 인덱스 위치

절차:

시작 및 범위 변수 정의

시작을 0으로 설정하고 범위를 a의 길이/크기로 설정합니다.

시작 <= 범위인 동안 다음을 수행합니다.

ㅏ. 중간 변수를 정의하고 (시작 + 범위)/2로 설정하면 중간 요소를 얻습니다.


비. x > a[mid]인 경우 시작 변수를 mid + 1로 설정합니다.


그렇지 않으면 x < a[mid] 범위 변수를 mid - 1로 설정합니다.


씨. a[mid] = x이면 mid를 반환합니다.

4. 값을 찾을 수 없으면 -1을 반환합니다.

샘플 코드:

다음의 인덱스 위치를 찾아봅시다.

public class MyClass {
  public static void main(String[] args) {
        System.out.print(binarySearch( new int[]{11, 88, 99, 111, 223, 999, 1028}, 999 ));
  }  

  public static int binarySearch(int[] a, int x){
    int start = 0;
    int range = a.length-1;

    while(start <= range){
        int mid = (start + range) / 2;

        if(x > a[mid]) start = mid + 1; 
        else if(x < a[mid]) range = mid - 1;
        else return mid;
    }
    return -1;
  }
}