[알고리즘] 이분 탐색 (Binary Search)

이분 탐색이란?

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.

이분 탐색의 구현

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 사용한다.

이 때, 처음 선택한 중앙값이 만약 찾는 값보다
크면 그 값은 새로운 최댓값이 되고,
작으면 그 값은 새로운 최솟값이 된다.

이분 탐색의 효과

선형 탐색의 시간 복잡도는 O(N)
이분 탐색의 시간 복잡도는 O(logN)
따라서 이분 탐색을 사용하면, 실행 시간을 단축할 수 있다.

References

이진 탐색이란?