JAVA 이진탐색 알고리즘 구성 과정과 장단점

🆕 개요

🍇 첫 번째 단계 : 논리 파악

이진 탐색의 논리구조 명료화

• 정렬된 배열이 있다고 가정한다.

• 제일 처음 중간 값을 찾고 비교한다.

• 타겟이 중간 값보다 작을 경우에는 끝 지점을 중간 값으로 새로 설정하고 처음부터 새로 설정된 끝 지점에서 다시 중간 값을 찾는다.
• 타겟이 중간 값 보다 작을 경우에는 이 논리가 반복 된다.

• 타겟이 중간 값보다 클 경우에는 첫 지점을 중간 값으로 새로 설정하고 새로 설정된 첫 지점에서 기존 끝 지점까지의 구간에서 새로 중간 값을 찾는다.
• 타겟이 중간 값 보다 클 경우에는 이 논리가 반복 된다.

기본 요소 코드 작성 1. 예제 배열을 생성 2. 타겟을 설정 3. 배열의 시작 점과 끝 지점 설정

• 0 부터 9까지의 정렬된 배열을 생성하였다.

• 타겟을 8로 정하고 상수로 선언하였다.

• 배열의 시작 인덱스는 ‘0’이므로 start변수로 초기화하였다.

• 배열의 끝 인덱스는 arr.length - 1 이므로 end 변수로 초기화 하였다.

• 그리고 중간 값은 자료 타입만 선언해 두었다.

🍉 두 번째 단계 : 기본 구조 구현

기본 논리 구조 코드 구현

• 중간값은 (시작점 + 끝점) /2 가 될 것이므로 사진대로 구성하였다.

• 세 가지의 경우가 발생가능하다.
• 중간 값이 타겟과 같은 경우
• 프로그램을 종료하고 안내문구를 출력
• 중간 값이 타겟보다 작은 경우
• 중간 값보다 높은 요소를 검색 해야하므로, 중간 값보다 인덱스가 1보다 높은 곳을 시작점으로 새로 설정한다.
• 중간 값이 타겟보다 클 경우
• 중간 값보다 낮은 요소를 검색 해야하므로, 중간 값보다 인덱스가 1보다 낮은 곳을 끝점으로 새로 설정한다.

코드 작동 확인

• 타겟을 바로 찾았을 때 작동확인

• 타겟이 중간 값보다 작았을 때 확인과 end값 없데이트 확인

• 타겟이 중간 값보다 클 때 확인과 start값 업데이트 확인

🥝 세 번째 단계 : 구조 반복

찾을 때 까지 같은 논리 구조를 반복하기

• 기본 논리 구조는 완성이 되었으므로, 찾을 때까지 같은 구조가 반복이 되면 된다. 이 환경에서는 while문이 가장 적절하다.

• 찾은 경우에만 반복을 끝낼 수 있도록 타겟과 중간 값이 같은지 비교하는 조건문에 break를 건다.

• 임의의 숫자를 넣고 한 번 돌려본다.

• 1회전에서 중간보다 큰값이 나오고 시작점이 5로 업데이트되었다.

• 2회전에서 중간값보다 큰 수중에서의 중간값 (중간중간값??)보다 작은수가 나왔다.

• 3회전에서 해당 수를 찾은 모습이다. 즉 코드는 잘 작동한다는 뜻이다.

• 그럼 다른 배열도 한번 대입해보겠다.

다른 수도 대입해보기

• 0부터 14까지의 배열을 생성해본다.

• 임의로 타겟은 4로 정하겠다.

• 돌려보자.

• 4회전만에 4를 찾았다. 잘 작동하는 것 같다!

🍓 결과 : 이진탐색 알고리즘 완성

최종 코드 구현

package ex03.test;

public class BinaryTest01 {
    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        final int target = 3;
        int start = 0;
        int end = arr.length - 1;
        int mid;
        int round = 0;

        while (true) {
            mid = (start + end) / 2;

            if (arr[mid] == target) {
                break ; // 값을 찾으면 반복을 종료한다.
            }
            if (arr[mid] < target) {
                start = mid + 1;
                round++;
            }
            if (arr[mid] > target) {
                end = mid - 1;
                round++;
            }
        }
        System.out.println("target값은 "+ mid + "이며, 총 " + round + "회전만에 찾았습니다.");
    }
}

• 좀 더 친절하게, 결과 값이랑 몇 회전 만에 찾았는지 안내 문구를 가다듬었다.

• 결과도 잘 작동한다.

• 이진 탐색 알고리즘 완성!

🤔 번외 : 랜덤 엑세스(2진 탐색)가 순차적 엑세스 보다 빠르다??

랜덤 엑세스와 순차적 엑세스의 의미란??

과연 항상 이진 탐색방식이 빠를까???

그렇다면 이진 탐색이 비 효율적이게 되는 변곡점은???