[Week3] 이분 탐색 (Binary Search)

이분 탐색(Binary Search)이란?

'정렬된 배열'에서 '특정 값'을 찾는 알고리즘을 의미

 

이분 탐색은 탐색 범위를 절반씩 줄여나가기 때문에 선형 탐색에 비해 빠른 속도를 보장한다. 

 

하지만, 배열이 정렬되어 있어야 한다는 조건이 필요하기 때문에 

배열이 정렬되어 있지 않은 경우에는 정렬 작업이 필요하다. 

 

이분 탐색 과정

1. 배열의 '중간 값'을 선택하여 찾고자 하는 값과 비교한다. 
2. 만약 중간 값이 찾고자 하는 값보다 크면 '배열 왼쪽 부분'에서 탐색을 다시 진행하고,
   중간 값이 찾고자 하는 값보다 작으면 '배열 오른쪽 부분'에서 탐색을 다시 진행한다. 
3. 중간 값이 찾고자 하는 값과 같으면 탐색을 종료한다. 

 

이분 탐색의 사용처

이진탐색은 데이터가 오름차순으로 정렬되어 있을 때 특정한 값을 찾아야 하는 경우에 사용한다. 

데이터의 양이 많은 경우에도 빠른 시간 내에 값을 찾을 수 있어 많이 활용되고 있다. 

 

이분 탐색의 성능

이분 탐색의 경우 시간 복잡도가 O(logn)으로 다른 정렬에 비해 상대적으로 매우 빠르다. 

 

이분 탐색 구현

public static int solution(int[] arr, int M) { // arr 배열에서 M을 찾자
	
    Arrays.sort(arr); // 정렬
	
    int start = 0;
    int end = arr.length - 1;
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2;
        if (M == arr[mid]) {
            return mid;
        }else if (arr[mid] < M) {
            start = mid + 1;
        }else if (M < arr[mid]) {
            end = mid - 1;
        }
    }
    throw new NoSuchElementException("타겟 존재하지 않음");
}

 

 

참고

https://adjh54.tistory.com/187

[Java/알고리즘] 이진 탐색(Binary Search) 이해하기