'binary search란' 태그의 글 목록

이진 탐색 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야 사용할 수 있는 알고리즘이다. 시작점, 끝점, 중간점을 활용하여 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적을 비교해 범위를 절반씩 좁혀가며 탐색하는 과정이다. 위와 같이 맨 처음 원소를 시작점, 마지막 원소를 끝점, 총 개수에서 2를 나눈 값을(소수점은 버린다) 중간점으로 둔다. 위와 같이 반씩 줄여가며 비교하다가 찾으려는 값과 중간점에 위치한 데이터가 같을 시 탐색을 종료한다. 절반씩 데이터가 줄어든다는 점으로 시간 복잡도는 O(logN)이다. 코딩 테스트에서의 이진 탐색 이진 탐색은 코딩 테스트에서 단골로 나오는 문제이고, 폭넓게 적용되기 때문에 난이도가 높고 구현할 코드량이 많아 실수하기 쉽다. 그래서 이진 탐색 코드를 암기하고..