이진 검색, 시간복잡도

Dec 20, 2023

Contents

1. 이진 검색

💡

정렬이 되어있는 데이터를 검색하는 방법 전체 데이터의 자리수/2 를 중간 값으로 하고, 이를 기준으로 찾고자 하는 값이 중간 값보다 크면 오른쪽, 작으면 왼쪽의 중간 값을 다시 구해 값을 찾는 방식


int[] arr = {0,1,2,3,4,5,6,7,8,9}

위의 배열에서 원하는 찾고자 하는 값이 7일 때,

총 10개의 값의 중간 값을 구한다.

중간 값 arr[min]= arr[10/2] = arr[5] =4 이렇게 구할 수 있다.

중간값을 기준으로 7>4 이기 때문에 4 이하의 값은 생략하고 5 이상의 값들로 다시 스캔한다.

중간 값 arr[min] = arr[7] = 7 이다.

찾고자 하는 값과 일치하기 때문에 스캔이 종료된다.

코드로 만들어보자.

우선 배열의 중간값을 찾아야 한다.


mid = start + ((end - start) / 2);

배열의 시작점 start =0 , 배열의 끝점 =10 이다.

첫번째 스캔 때는 변함이 없지만, 두번째 스캔부터 값이 변경된다.

만약 원하는 값이 중간 값보다 작다면 배열의 왼쪽을 스캔해야 하기 때문에 end값을 변경한다.

end 값은 중간값보다 하나 작은 값이 된다.


if(arr[min]>target){ 
		end = mid - 1 ;
}

반대로 원하는 값이 중간 값보다 크다면 배열의 오른쪽을 스캔한다. 이때는 end 값은 그대로지만 start 값이 mid 위치에서 +1 증가한다.


if(arr[min]<target{
			start= mid + 1 ;
	}

이제 반복문으로 합쳐보자


public static void main(String[] args) {

        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        Scanner sc = new Scanner(System.in);
        System.out.print("원하는 값을 입력하세요:");
        int target = sc.nextInt();

        int start = 0;
        int end = arr.length - 1;
        int mid;
        int count = 0;

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

            if (arr[mid] == target) {
                break;
            } else if (arr[mid] < target) {
                start = mid + 1;
            } else if (arr[mid] > target) {
                end = mid - 1;
            }
        }
        System.out.println("타겟의 위치는 " + mid);
        System.out.println("검색 횟수 :" + count);
    }

반복이 언제 종료될지 모르기 때문에 while 반복문을 사용했다.

배열의 시작점의 인덱스는 0 , 끝점의 인덱스는 데이터의 수 -1 이다.

반복문이 돌 때 마다 mid 값을 변경해 target 값과 arr[min] 값이 일치할 때 break 로 코드를 종료한다.