[알고리즘 / Python] 이분 탐색 / 이진 탐색 (Binary Search)
이분 탐색이란, 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘이다. 1. 이분 탐색의 조건 반드시 오름차순으로 정렬된 상태에서 시작해야 한다. 2. 이분 탐색 알고리즘 시간복잡도: O(logN) 반복문과 재귀 두 가지 방법을 사용할 수 있다. 자료를 오름차순으로 정렬한다. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다. mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다. ⓐ target이 mid 값 보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색) ⓑ target이 mid 값 보다 크면 start를 mi..
Study/Algorithm
2023. 1. 17.