[algorithm] 선형 검색과 이진 검색

올바른 알고리즘을 선택하는 것이 어플리케이션의 속도를 상당히 향상시킨다.

 

search 알고리즘

 

linear search(선형 검색) 

순서대로 목표값을 찾는다.
어느 배열에서나 사용 가능
최악의 경우
우리가 찾는 목표값이 배열에 없거나 배열에 마지막에 있을때
목표값이 뒤에 있을수록 시간이 많이 걸린다.

 

binary search(이진 검색)
정렬된 배열에서만 사용가능하다.
정가운데부터 시작해서 목표값과 비교하면서 찾는다. 
다시 정가운데로 가고 이것을 반복
정렬된 배열에 데이터를 추가하는 것은
정렬되지 않은 배열에 데이터를 추가하는 것보다 시간이 많이 걸린다.
정렬을 해야하기 때문에(비교하고 배열의 요소들을 옮겨야하기 때문)