이분 탐색(Binary Search)

소개

• 정렬된 배열에 특정 원소가 존재하는지를 O(log n)의 시간에 파악할 수 있는 알고리즘.
• 구현은 반반반 방법과 매 라운드마다 폭을 줄이며 건너뛰는 방법이 있다.
• 반반반 방법은 흔히 볼 수 있는 구현방법이다.
  • 매 단계마다 배열의 중앙값을 살펴본다.
  • 중앙값이 찾는 값이면 true를 반환한다.
  • 중앙값과 찾는 값이 다르면, 중앙값과 대소비교를 통해서 탐색 배열을 절반으로 줄인다.
  • 마지막 단계까지 찾지 못하면 해당 배열에 찾는 값이 없음을 의미한다.

구현

// 반반반 구현
public boolean binarySearch(int[] arr, int target) {
    int start = 0;
    int end = n - 1;

    while(start <= end) {
        int middle = (start + end) / 2;
        
        if(arr[middle] == target) return true;
        
        if(arr[middle] > target) {
        	end = middle - 1;
        } else {
        	start = middle + 1;
        }
    }
    return false;
}