[자료구조]Linear Search VS Binary Search

Linear Search

장점

• sorted 되어있지 않아도 상관없음
• 정렬이 필요없으니 item 추가 시 시간이 소요되지 않음

단점

• 기본적으로 오래 걸림. N개의 array의 경우 최악의 경우 N개를 모두 열람해야 하는 비효율적인 작업을 동반.

Binary Search

• binary는 0과 1이 아니라 반으로 쪼개는 것을 의미

장점

• 긴 array의 data를 다룰 때 매우 효율적

단점

• Sorted array에서만 가능
• item 추가 시 $O(1)$ 이 아님.

과정

• 배열의 중간의 값 n을 가정
• target이 n보다 큰지 작은지 판단 (n<target)

예시 - target 값 9

1~10 array 가정
총 3 step
1. 5에서 시작
2. 9>5 이므로 6~10범위로 이동
3. 남은 범위에서 중간값 선택(8)
4. 9>8 이므로 9~10 범위로 이동
5. 최종값 9 선택

위 예시에서는 선형검색시 9 step이 필요함.

• 10,000개의 데이터셋의 경우
  Linear search : 10000step
  Binary search : $log_210000 =14.xx$

-> 매우 큰 차이가 남.

Reference

• https://youtu.be/WjIlVlmmNqs