자료구조 - 배열 (Array)

배열은 같은 타입의 순서가 있는 자료구조이다.

- 배열은 동일한 타입의 원소들을 메모리상에 연속적으로 저장한다.
- 각 원소들은 동일한 데이터 타입을 가지고 있다.
- 배열은 크기를 가지고 있어서 배열에 데이터 원소가 얼마나 들어있는지 알 수 있다.
- 특정 데이터가 배열의 어디에 있는지 알려주는 숫자인 인덱스가 있다.
- 인덱스로 각 요소에 빠르게 접근할 수 있다.

 

컴퓨터는 배열을 할당할 때 어떤 메모리 주소에서 시작하는지 기록해 둔다. 그래서 시작 메모리 주소에서 얼마나 떨어져있는지로 배열의 값에 바로 바로 접근할 수 있다.

 

선형 검색 (linear search)

메모리 주소에는 한 번에 접근할 수 있지만, 각 메모리 주소에 저장된 값은 쉽게 알 수 없다. 그래서 특정 값이 배열 안에 있는지 확인하려면 배열의 모든 요소를 하나씩 확인해야 한다. 이러한 방법을 선형 검색이라고 하는데 이는 배열의 모든 요소를 하나씩 확인하면서 찾는 값과 일치하는지 확인한다.

 

이진 검색 (binary search)

이진검색은 원하는 값을 찾을 때까지 검색할 데이터의 범위를 반씩 줄여가며 찾는 알고리즘이다. 정렬된 배열에서만 사용할 수 있으며, 이것은 정렬된 배열의 장점 중 하나이다. 이진 검색은 선형 검색보다 훨씬 빠르게 원하는 값을 찾을 수 있으며, 검색 속도가 빠른 만큼 더 많은 데이터를 처리할 수 있다.