이진 탐색

이진 탐색

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

 

이진 탐색 핵심 이론

1.  현재 데이터셋의 중앙값을 선택한다.
2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
4. 과정 1 ~ 3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

시간복잡도

O(logN)

 

코드 예시

int start = 0;
int end = arr.length - 1;
while(start <= end) {
	int mid = (start + end) / 2;
    int midv = arr[mid];
    if(midv > target) {
    	end = mid - 1;   // 핵심 : 중간값이 찾고자하는 값보다 크면 end를 바꿈
    } 
    else if (midv < target) {
    	start = mid + 1;  // 핵심 : 중간값이 찾고자하는 값보다 작으면 start를 바꿈
    }
}