[자료구조] 선형 검색과 이진 검색

선형 검색

인덱스를 하나씩 증가시켜 확인하는 방법.

배열의 사이즈가 n이면 찾는 값이 제일 첫 번째 값이면 1단계만에 끝낼 수 있지만 마지막에 존재하면 n단계나 필요함.

정렬이 안 되도 사용가능

 

이진 검색

배열의 중간값의 인덱스의 값보다 큰 지 작은 지 확인. 크면 작은 값을, 작으면 큰 값을 전부 배제해 나아가며 진행. 

 

예시) [1, 2, 3, 4, 5, 6, 7, 8] 에서 1를 원한다고 가정.

1. 중간 인덱스 4보다 1이 작기 때문에 [1,2,3]에 존재함을 판단.

2. 중간 인덱스 2보다 1이 작기 때문에 [1]에 존재함을 판단.

3. 중간 인덱스 1이 1과 같기 때문에 인덱스를 반환.

 

배열의 사이즈가 n일 때 2^k보다 작거나 같으면 최대 k단계만에 판별이 가능하다.

 

예시) 위 예시의 배열 사이즈는 8인데 이는 2^3보다 작거나 같기 때문에 최대 3단계만에 판별이 가능하다.

 

그러나 정렬이 필수이다.

 

선형 검색 vs 이진 검색

100개의 값을 갖는 배열인 경우 최대 단계수는 각각 다음과 같다.

 

선형 검색: 100단계

이진 검색: 7단계

 

이는 값이 커지면 커질 수록 차이가 커진다.

1000개의 값일 경우

 

선형 검색: 1000단계

이진 검색: 10단계

 

을 가진다.

 

이처럼 정렬된 배열은 삽입은 다소 느리지만, 검색은 훨씬 빠르다.