이진 탐색 (Binary Search)

 

탐색의 방법은 크게 두가지가 있는데, 선형 탐색과 이진 탐색이 있습니다.

그 중 이진 탐색 방법에 대해 작성을 해봤습니다.

 

 

이진 탐색(Binary Search)

- 정렬된 상태에서 사용할 수 있습니다.

배열의 정 중앙값을 선택해 그 값보다 작으면 왼쪽 배열, 크면 오른쪽 배열에서 재귀를 돌려 결국 원하는 값을 탐색할 때 사용하는 방법입니다.

 

ex) int[] arr = {1,2,3,4,5,6,7,8,9} 에서 이진 탐색으로 숫자 6을 찾아라.

1) 중앙값인 5보다 원하는 값이 크기 때문에 우측 배열을 재귀로 돌아야 합니다. {6,7,8,9}

2) 중앙값인 7보다 원하는 값이 작으니 좌측 배열을 재귀로 돌아야 합니다. {6}

3) 중앙값인 6과 원하는 값인 6이 일치하기 때문에 종료된다.

3번째 만에 원하는 값을 탐색하였습니다.

 

시간복잡도

이진 탐색 : O(log n)

 

* 선형탐색은 정렬 되지 않은 상태, 이진 탐색은 정렬된 상태에서 사용하는게 좋습니다.