Binary Search (이진검색)

이진검색이란?

• 원소가 오름차순 또는 내림차순으로 정렬된 배열에서 원하는 키값(또는 위치)을 찾아내는 알고리즘
• 배열은 정렬되어 있어야 한다.
• 정렬된 배열의 중간 임의의 값을 기준으로 찾고자하는 값의 크고 작음을 비교한다.
• 선택한 중간 임의이 값이 찾는 값보다 크면 그 값은 새로운 최대값이되고, 작으면 새로운 최소값이 된다.

예제

 

재귀함수로도 구현할 수 있다.

 

시간복잡도

• O(logN)