[TIL] 220124

이분탐색(이진탐색)

배열 또는 리스트를 탐색하는 방법

배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다.

구현

탐색해야 할 리스트 Integer[] = array가 있을 때, 인덱스 마지막 값을 end, 첫번째 값을 start라고 한다.

 

start, end는 탐색할 시작점과 종료점이 된다.

start = 0

end = n-1 = 14

 

 

이분탐색을 위한 mid 값을 구한다.

mid = (start + end)/2

 

 

이때 구하고자 하는 값 k의 값이 9일 경우, 

array[mid]의 값은 7이므로 array[mid] < k이다.

이럴경우 start = mid+1로 재설정한다.

 

1. array[mid] > k    : end = mid-1
2. array[mid] < k    : start = mid + 1
3. array[mid] == k  : 탐색 종료

 

 

 

 

 

 

Referrence

 

https://minhamina.tistory.com/127

이진탐색 = 이분탐색 (Binary Search) - Java로 구현