이진 검색 (Binary Search)

| 이진 검색 - Binary Search

이진 검색은 정렬된 배열의 중간점을 찾아가며 배열을 쪼개서 원하는 값을 찾아내는 검색 알고리즘이다.

시간 복잡도는 O(log n) 을 가지며 선형 검색 O(n) 보다 속도는 빠르다.

하지만 데이터가 정렬이 되어있어서 이진 검색을 사용 할 수 있다.

또한 데이터의 갯수가 적다면 선형검색이 더 효과적일 수 있다.

주의 할 점은 데이터는 무조건 분류 되어있어야 한다.

분류가 되어있지 않다면 이진 검색은 아무런 쓸모가 없다.

알고리즘은 친구들과 업앤다운 게임을 생각해보면 굉장히 이해하기 편하다.

1부터 50까지의 숫자를 맞추는 게임이며 정답은 27이다.

나는 23을 제시하고 친구는 23 보다 27이 높으니 "업" 이라고 외쳤다.

그러면 1부터 23은 필요없는 숫자가 되며 선택지는 24부터 50까지로 줄여진다.

이진 검색 또한 업앤다운 게임과 비슷하지만 처음 내가 제시하는 정답이 배열의 중간 index 이다.

 

| 이진 검색 예시

시작점과 끝점 그리고 중간점은 항상 바뀌어야 한다.

while문을 사용해서 중간값을 target과 계속 비교하며 값을 찾는다.

시작점이 끝보다 높으면 해당 값은 없는것이기 때문에 -1 을 리턴하도록 했다.

 

| 이진 검색의 빅오 (Big O)

이진 검색은 평균적으로 O(log n) 의 시간을 가지지만

정말 운이 좋게 찾아야 하는 값이 중간지점이라면 상수시간 = O(1) 을 가질 수 있다.