자바알고리즘 (3) 이진 탐색

 

 

 

이진 탐색(Binary Search)은 정렬된 배열이나 리스트에서 

특정값을 찾기 위해 사용되는 효율적인 알고리즘이다 

이진 탐색의 핵심 아이디어는 검색 범위를 절반으로 줄여가면서 값을 

찾는 것이다 

 

이진 탐색의 동작 원리 

정렬된 배열을 가정한다 

오름차순 혹은 내림차순인 경우 

 

배열의 중간값을 계산한다 

(왼쪽인덱스 + 오른쪽인덱스) / 2 

 

찾고자 하는 값이 중간값과 같으면 검색이 성공한다

 

찾고자 하는 값이 중간값보다 작으면 검색 범위를 

중간값 기준으로 왼쪽 절반을 줄인다 

 

찾고자 하는 값이 중간값보다 크다면 검색 범위를 

중간값 기준으로 오른쪽 절반을 줄인다 

 

 

 

public class Practice {
    public static void main(String[] args) {


        Scanner sc = new Scanner(System.in);
        int search = sc.nextInt();

        int[] a = new int[]{39,41,53,55,68,72,84,88,92,97};


        int left = 0;
        int right = a.length -1;
        int pos = -1;

        // 53을 입력한다는 전제

        while (pos == -1 && left <= right){
            // left가 right보다 커지거나 같지 않은 경우 반복문을 종료
            int middle = (left + right) / 2;
            // 4 index를 가지고 있다.
            if (a[middle] == search){
                pos = middle;

            } else if (a[middle] > search) {
                right = middle - 1;
            }else {
                left = middle + 1;
            }
        }
        System.out.println(pos);

    }
}

 

1. 53을 입력시 

53과 a[middle] a배열 middle 인덱스 요소의 값이 같은 경우 

 

pos를 middle 인덱스 값으로 재할당 

 

a[middle] 요소의 값과 search[53] 같지 않을 겨우 

 

a[middle] 값이 search == 53 보다 

값이 클 경우 

 

else if (a[middle] > search) {
    right = middle - 1;

 

right를 middle[현재 4] - 1; 즉 3으로 초기화 

 

int middle = (left + right) / 2;

 

다시 left는 0 

right는 3 

3 / 2 = 1 [소수점 버림]

 

다시 검색 대상을 뒤쪽으로 부터 반을 줄여서 검색을 한다 

이 때 middle은 1

a[middle]은 배열의 1 인덱스를 가르킨다 

 

a[middle] = 1번 인덱스 41과 사용자에게 입력 받은 53을 비교한다 

41 > 53의 조건은 거짓이므로 else문이 실행된다 

 

(현재 right는  3)

left = middle + 1; 

 

현재

middle(left(2) + right(3)) / 2

a[middle]의 요소값과 일치하게 되므로 

if문 조건이 참이 되므로

pos에 현재 middle (2) 를 대입

 

while문 조건이 거짓이 되므로 반복문은 

종료 

pos는 2를 출력하게 된다.