이진탐색

이진탐색이란?

원하는 데이터를 빠르게 찾기 위한 알고리즘
이진 탐색은 데이터가 정렬되어있는 상태에서 중앙값을 이용해서 찾고자 하는 값과 비교해가며 찾는 알고리즘
(코딩테스트에서 부분 문제로 많이 출제 됨)

기능	특징	시간복잡도
Target 데이터 탐색	중앙값 비교를 통한 대상 축소 방식	O(logN)

 

이진탐색 핵심이론

pre) 오름차순으로 정렬

1. 현재 데이터 셋에서 중앙값을 설정한다
2. 중앙값 > Target 값 일때, 중앙값 기준으로 왼쪽 데이터 셋 설정
3. 중앙값 < Target 값 일떄, 중앙값 기준으로 오른쪽 데이터 셋 설정
4. 1~3을 반복하다가, 중앙값 == Target 일때 탐색 종료 

• EX) 48을 찾아라

20	30	33	40	45	48	50
x	x	x	x	45	48	50
x	x	x	x	x	48 (탐색 종료)	50

 

이진탐색 구현

import java.util.Arrays;

public class App {
    public static void main(String[] args) throws Exception {
        int[] arr = new int[] {30,20,10,60,40,50};
        Arrays.sort(arr);
        int findNum = 40;

        int result = binarySearch(arr, findNum);

        if(result != -1){
            System.out.println("찾은 수 (정렬된 인덱스 값): " + result);
        }else{
            System.out.println("해당 수를 찾을 수 없습니다");
        }
    }

    private static int  binarySearch(int[] arr, int findNum){
        int low = 0;
        int high = arr.length - 1;

        int middle = 0;

        while(low <= high){
            middle = (low + high) / 2;
            if(arr[middle] == findNum){
                return middle; // 찾음
            }else if (arr[middle] > findNum){
                high = middle - 1; // 왼쪽 데이터 셋 찾기
            }else{
                low = middle + 1; // 오른쪽 데이터 셋 찾기
            }
        }

        return -1;
    }
}