👀 'Do it! 알고리즘 코딩테스트 with Python(김종관 저)'을 공부하고 정리한 내용입니다.

1. 선형 탐색

이건 그냥 하나하나 순서대로 찾아보는 겁니다.

• 위와같은 리스트에서 원하는 수를 찾기 위해 왼쪽에서 하나씩 하나씩 이동합니다.

• 만약 원하는 값을 찾았다면, 더이상 탐색하지 않고 끝냅니다.

선형 탐색은 언제 쓸까?

만약 리스트가 정렬되지 않은 상태라면, 그리고 정렬할 수 없다면, 선형탐색을 쓸 수 밖에 없습니다.

2. 이진 탐색

이진탐색은 데이터가 정렬 되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 입니다.

대상 데이터의 중앙값과 찾고자하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾습니다.

이진 탐색 수행과정

1. 현재 데이터셋의 중앙값을 선택한다.
2. 중앙값과 찾고자하는 데이터의 비교에 따라 중앙값 기준 왼쪽 또는 오른쪽 데이터를 선택한다.
3. 1-2를 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

위처럼 이진탐색을 사용하면 N개의 데이터에서 최대 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있습니다. 예를 들어 16개의 데이터가 있으면, 최대 4번의 연산으로 원하는 데이터의 위치를 찾을 수 있습니다.