개요

• 리스트에서 검색을 하는 방법에는 2가지가 있다.
• 선형 검색과 이진 검색이 그것이다.

선형 검색

• 선형 검색은 리스트 전체를 하나씩 순회하면서 검색하는 방식이다.
• 선형 리스트와 연결 리스트 모두에서 사용할 수 있다.
• 시간 복잡도는 O(n), 공간 복잡도는 O(1)이다.
  

이진 검색

• 이진 검색은 검색할 범위를 반으로 줄여가며 검색하는 방법이다.
• 이진 검색은 정렬된 선형 리스트에서 사용할 수 있다.

1. 시간 복잡도는 O(logn)
2. 공간 복잡도는 O(1)
   
   

LowerBound

• 작아지는(Lower) 지점(Bound)을 찾는 것이다.

• 모든 값들이 유일하지는 않고, 중복되는 값이 있을 수 있다.

• LowerBound를 이용하면 특정 값보다 작거나 같은 원소가 처음으로 발견되는 지점을 찾을 수 있다.

• 아래와 같은 리스트에 LowerBound(3)을 한다면 빨간색 화살표의 인덱스를 반환한다.
  

• 코드로 구현하면 아래와 같다.
  

UpperBound

• 커지는(Upper) 지점(Bound)을 찾는 것이다.

• 모든 값들이 유일하지는 않고, 중복되는 값이 있을 수 있다.

• UpperBound를 이용하면 특정 값보다 크거나 같은 원소가 처음으로 발견되는 지점을 찾을 수 있다.

• 아래와 같은 리스트에 UpperBound(3)을 한다면 빨간색 화살표의 인덱스를 반환한다.
  

• 코드로 구현하면 아래와 같다.
  

라이브러리

• 이진 검색의 경우 이미 라이브러리에 추가되어 있으며 Array.BinarySearch() 혹은 List.BinarySearch()를 사용하면 된다.