선형검색

• 찾고자하는 값을 인덱스 0번부터 하나하나씩 검색해가며 찾는 방식을 말한다.

• 예를들어 [1, 3, 87, 135, 1003] 배열이 있고 1003 값을 찾는다고 가정해보자

• 인덱스 0번부터 1003 값이 들어있는지 확인한다. 0,1,2,3번까지는 같은 값이 없기 때문에 넘어간다.

• 4번을 검색했을 때 같은 값이 존재하기 때문에 검색을 멈춘다.

이진검색

• 정렬된 배열을 절반씩 나누어 검색해가는 방식을 말한다.
• 예를들어 [1, 3, 4, 13, 78, 101, 134, 141, 200] 배열이 있고, 200을 찾는다고 가정해보자
• 먼저 가운데 값부터 검색을 시작한다. 값이 78 이므로 왼쪽에 있는 값들을 배제시킨다.
• [101, 134, 141, 200] 남은 값들 중에 가운데 값이 두 개이므로 임의로 왼쪽 값을 선택한다.
• 134를 기준으로 왼쪽값은 아니기 때문에 오른쪽 값들을 비교해본다.
• [141, 200] 남은 값을 확인한다.
• 141은 아니기 때문에 배제시키고 200을 확인한다.

비교

• 작은 단계의 경우 두 검색을 비교했을 때 어떤 알고리즘이 더 낫다는 점은 없다. 하지만 단계 수가 많아지면 두 검색 사이에 차이가 있다.

• 선형검색이 100단계 걸린다고 가정했을 때 이진검색은 7단계 밖에 걸리지 않는다.

• 선형검색은 찾는 값이 마지막에 있다고 하면 100단계가 걸리지만 이진검색의 경우 절반의 값을 제거 할 수 있기 때문에 7단계 밖에 소비되지 않는다.
  

• 그래프를 살펴보면 원소 수가 늘수록 선형검색은 단계 수가 기하급수적으로 늘어나는 것을 볼 수 있다.

• 검색 시간을 보자면 시간이 많이 걸리는 선형검색이 쓸모 없어 보이지만 정렬되지 않는 배열에서는 선형검색을 사용해야 한다.