[알고리즘] 이진탐색

이진탐색이란

• 정렬된 배열에서 특정한 값을 찾기 위한 목적으로 사요하는 알고리즘이다.

논리

• 정렬이 되어 있다는 것을 전제로한다.
• 찾고 싶은 값을 설정한다.
• 중간 인덱스 값을 찾는다.
• 찾고 싶은 값을 중간 인덱스 값과 비교한다.
  • 값이 동일하다.
    • 탐색이 완료된다.
  • 중간 인덱스 값이 크다.
    • 찾는 값은 왼편에 있다는 뜻이다.
    • 왼편에 있는 값들 중 중앙 값을 찾는다.
    • 다시 값들을 비교한다.
  • 중간 인덱스 값이 작다.
    • 차는 값은 오른편에 있다는 뜻이다.
    • 오른편에 있는 값들 중 중앙 값을 찾는다.
    • 다시 값들을 비교한다.

이미지로 보기

특징

• 탐색하는 로직들 중 가장 빠르다.
• 탐색 범위를 절반씩 줄여나가기 때문에 선형 탐색에 비해 빠르다.
• 데이터가 많은 경우에도 빠르게 찾을 수 있다.

단점

• 데이터의 정렬이 선행된다.

예제

• [1,2,3,4,5] 중 2를 찾아보자.

예제 코드

// 크기가 5인 배열선언
int[] arr = new int[5];

// 배열에 데이터 넣기
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
arr[4] = 5;

// 찾고자 하는 값
int key = 2;

// 찾고자 하는 값의 인덱스 번호
int keyIndex = -1;

// 배열의 시작 인덱스
int start = 0;

// 배열의 마지막 인덱스
int end = arr.length - 1;

// 탈출 할 때 까지 도는 반복문
while (start <= end) {

    // 중앙 인덱스를 설정
    int mid = (start + end) / 2;

    // 중앙 인덱스 값이 찾고자 하는 값이라면
    if (arr[mid] == key) {

        // 중앙 값 인덱스 저장
        keyIndex = mid;

        // 반복문 탈출
        break;

    }
    // 중앙 인덱스 값이 찾고자 하는 값보다 크다면
    else if (arr[mid] > key) {

        // 찾는 값이 왼쪽에 있다는 뜻이므로
        // 최대 인덱스를 중앙 인덱스의 왼쪽(-1) 인덱스로 잡는데
        end = mid - 1;

    }
    // 중앙 인덱스 값이 찾고자 하는 값보다 작다면
    else if (arr[mid] < key) {

        // 찾는 값이 오른쪽에 있다는 뜻이므로
        // 최대 인덱스를 중앙 인덱스의 오른쪽(+1) 인덱스로 잡는데
        start = mid + 1;

    }

}

// keyIndex가 초기 값 그대로라면
if(keyIndex == -1) {

    // 값이 존재하지 않는 것이다.
    System.out.println("찾는 값이 없습니다.");

}
else {

    System.out.println(arr[keyIndex]);    

}