[Algorithm] 이분 탐색(Binary Search)

이분 탐색

탐색 범위를 두 부분으로 분할 하면서 검색하는 방식

알고리즘

1. 오름차순 정렬
2. 배열 포인터 인덱스 start, end, mid 값 설정
3. mid와 내가 구하고자 하는 값과 비교
4. 같으면 mid가 답
5. 구할 값이 mid 보다 작으면 start = mid + 1
6. 작으면 end = mid - 1
7. start > end가 될 때까지 반복

public class binarySearch {
    public int solution(int n, int m, int[] arr){
        Arrays.sort(arr);
        int start = 0;
        int end = n -1;
        int mid = 0;
        while(start <= end){
            mid = (start + end) / 2;
            if(arr[mid] == m) return mid+1;
            else if (arr[mid] < m) start = mid + 1;
            else end = mid - 1;
        }
        return -1;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // n개의 숫자 입력
        int m = sc.nextInt(); // m이 n개의 숫자 중 몇번째에 있는지 탐색
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }
        System.out.print(new binarySearch().solution(n, m, arr)); // m의 위치 출력. 없으면 -1 출력
    }
}

시간 복잡도

전체 탐색: O(N)
이분 탐색: O(logN)