Binary Search VS Linear Search

 

Linear Search(선형검색 알고리즘)

- 0부터 차례로 확인, 순서대로 차근차근

- 최악: 맨 마지막에 위치, 존재하지 않은 값

Linear Time Complexity

 

Binary Search(이진검색 알고리즘)

- 조건: Sorted Array(정렬된 배열)

- Sorted Array는 데이터 추가 시간이 오래 걸림: 하나하나 값 비교 후 추가

- Binary: 두 개로 쪼개는 것

 

1) 전체의 중간에서 검색 시작(정중앙)

2) 중간 값과 target 비교

3) 비교 후 조건에 충족하는 쪽의 중간 값과 다시 비교

  -> 반씩 범위를 좁힘

 

예) target: 8

1	2	3	4	5(step 1)	6	7(step 2)	8(step 3)	9
				5 < 8		7 < 8	8=8

* 이진검색: 3steps/선형검색: 8steps (1부터 차례로 검색)

 

-> 거대한 배열을 다룰 때 효율적(정렬 필요)