binary search

이진 탐색이란 데이터가 모두 정렬된 상태에서 탐색 범위를 절반씩 쪼개면서 탐색을 진행하는 알고리즘이다. 즉, 이진 탐색은 중간지점 (이하 중간점) 의 데이터를 찾고자 하는 데이터와 비교하여 탐색 범위를 좁힌다는 특징을 갖고 있다. 여기서 중간점 = (시작점 + 끝점) // 2 의 식으로 구하게 되며, 이때 // 는 버림 나눗셈 연산자로 나눗셈을 진행하고 몫의 정수 부분만 취하는 파이썬 연산자이다. 이진 탐색을 진행하는 과정을 살펴보자. 0 1 2 3 4 5 6 7 8 9 위와 같이 오름차순 정렬되어 있는 데이터가 있다고 가정하자. 여기서 우리는 3이라는 데이터가 어디에 위치해있는지를 탐색하고 싶다. 가장 먼저 시작점 = 0, 끝점 = 리스트의 마지막 인덱스 로 초기화 한다. 중간점 = (시작점 + 끝점)..

이진 탐색 알고리즘을 들어가기 전에 먼저 순차 탐색 (Sequential Search) 에 대해서 알아보자. 순차 탐색이란 말 그대로 리스트 내에서 특정 데이터를 찾고 싶을 때, 앞에서부터 순차적으로 데이터를 비교해서 탐색하는 알고리즘이다. 즉, 리스트내의 모든 데이터에 접근하며 차례대로 확인하게 된다. 따라서 시간이 여유롭다면 데이터의 개수가 아무리 많더라도 반드시 원하는 데이터를 찾아낼 수 있다는 장점이 있다. 순차 탐색 알고리즘이 수행되는 곳은 정말 다양하다. 아래의 경우에도 순차 탐색이 사용된다. 리스트에 특정 값의 원소가 있는지 체크할 때 리스트에서 특정 값을 가지는 원소의 개수를 구할 때 ( count() 메서드 ) 순차 탐색 알고리즘의 소스코드는 아래와 같다. 순차 탐색의 시간 복잡도는 다음..