[이분 탐색] 알고리즘 설명 및 예제 풀이
이분 탐색(Binary Search) 이분 탐색은 코딩 테스트에 많이 출제되는 문제 중 하나입니다. 이분 탐색의 주요 조건은 정렬되어 있는 배열입니다. 순차탐색의 경우 배열의 처음부터 끝까지 배열의 모든 원소를 체크합니다. 이분탐색은 탐색 범위를 절반씩 줄여가며 찾아가는 탐색 방법입니다. 예를 들어보겠습니다. [ 9, 4, 2, 5, 3, 8 ] 다음과 같은 리스트가 주어졌을 때 숫자 2를 찾는다고 가정해 보겠습니다. 이분탐색을 위해 먼저 정렬을 해줍니다. [ 2, 3, 4, 5, 8, 9 ] 먼저 배열의 중간에 위치한 5와 2를 비교합니다. 2는 5보다 작으므로, 탐색 범위를 5의 왼쪽에 있는 원소들로 줄일 수 있습니다. 이제 탐색 범위는 [ 2, 3, 4 ]이 됩니다. 이번에는 중간 원소인 3과 2를..
2019. 9. 10.
