이진 탐색 알고리즘

이진 탐색 알고리즘

 13개의 원소를 가진 수열에서 찾고자 하는 값이 35가 있는지를 찾아야 합니다. 

 

해당 위치 index를 반환하고 없으면 0을 반환하면 됩니다. 

binary_Search 검색 방법을 보면 제일 처음에 중간 index를 계산을 합니다. 시작 index가 1이고 마지막 index가 13이고 이에서 2를 나누면 가운데 값을 찾게 됩니다. 

 

찾고자 하는 값은 key값으로 35입니다. 이 35라는 값이 왼쪽에는 없기 때문에 제외를 하고 오른쪽 부분에서 이진 탐색 부분을 재귀적으로 호출해서 찾으면 됩니다. 

 

이진탐색 알고리즘은 다음과 같습니다.

이진탐색의 시간복잡도는 앞에 살펴 본 마스터 정리로 볼 수 있습니다. 

 

합병 정렬의 복잡도