학습 목표
주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있다.
0. 인트로
- 배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조이다. 컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나에 접근한다.
만약 어떤 값이 배열 안에 속해 있는지를 찾아보려면 배열이 정렬되어 있는지의 여부에 따라 다른 방법을 사용할 수 있다.
1. 선형 검색
- 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사하는 것이다.
- 케비넷에서 숫자 50을 찾기 위해 Eric이 첫번째 사물함부터 마지막 사물함까지 문을 하나씩 차례대로 열어봤던 장면을 떠올려보자.
2. 이진 검색
- 배열이 정렬되어 있다면, 배열의 중간 인덱스부터 시작해서 찾으려고 하는 값과 비교하여 그 값보다 작은 값이 저장되어 있는 인덱스 혹은 큰 값이 저장되어 있는 인덱스 쪽으로 이동하고 이를 반복한다.
- 숫자가 정렬 돼있는 상태에서, Nizari가 가운데 사물함을 열었을 때 나온 숫자와 숫자 50을 비교하여 왼쪽 사물함을 열어볼지 오른쪽 사물함을 열어볼지 선택하고 이 과정을 반복했던 장면을 떠올려보자.