[Algorithm & Data Structure] 검색 알고리즘 (Binary Search & Linear Search)

// "Normad Coder의 알고리즘과 데이터 구조 강의" 듣는 중//

​

• 데이터 구조를 선택하는 것처럼 어떤 알고리즘을 선택할 지도 고민해야 함. 그 합이 중요하니까.
• 알고리즘은 작업을 실행하기 위한 단계의 리스트! 레시피처럼
• 시간 복잡도에 따라서 적은 step이 언제나 better

​

Search Algorithm

• Binary Search & Linear Search
• 검색을 최대한 빨리하는 것이 목적.

​

​

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

• 검색에서 가장 자연스러운 것, 어느 배열에서나 쓸 수 있음.
• 1번 아이템부터 순서대로 목표를 찾음. but, 최악의 시나리오는 찾는 항목이 배열에 끝에 있거나, 배열에 아예 없는 경우
• => 배열이 커질수록 선형 검색을 하는 시간이 길어짐.
• => linear time complexity: 인풋이 많을수록 수행 시간도 선형적으로 증가함
• 대안으로,

​

 

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

• 모든 배열에 쓸 수는 없고, sorted array(정렬된 배열)에만 가능함
• sorted array는 순서대로 정열 된 것; 예, 작은 수에서 큰 수처럼
• so, 데이터를 추가할 때는 정렬되지 않은 배열보다 시간이 오래 걸림.
• 어디에 넣을지 하나씩 비교하고, 그 공간을 비우려면, 전부다 오른쪽으로 넘겨야 함.
• but, 추가에는 오래 걸려도 대신 검색 시에는 굉장히 빠름.

​

• binary가 이진법이 아니라 반으로 쪼개는 것을 의미함.
• 리니어는 처음부터 시작하지만 바이너리는 중간부터 체크를 시작함. taget이 찾는 것보다 큰지 작은지를 확인함.
• 목표보다 크면 왼쪽으로 가고, 작으면 오른쪽으로 가는 것. 이 작업을 target을 찾을 때까지 반복하는 것.

​

• 예,

1. 1-10 중 9(target)를 찾을 때, 5부터 찾고(중간), 왼쪽은 무시하고 오른쪽으로 가는 데
2. 다시 거기에서(5-10) 중앙인 8에서 target인 9와 크기를 비교해서 오른쪽으로 감.
3. 그럼 3번째 선택에서 9, 10 밖에 없어서 target을 바로 찾아냄. but, linear는 9번의 시도가 필요함.

=> 만약 1-20이면, 4번째 스텝만에 찾음(찾을 때는 target 2개 중 비교하는 것까지 가야 함. )

​

• => 반절을 날리고 시작해서 데이터가 2배가 되어도 필요한 스텝은 +1일뿐
• => 큰 데이터 처리할 때 매우 편함. 예, 리니어는 1만 개면 1만 개 걸리는 데, 바이너리는 14개 스텝이면 됨
• 스피드 매우 빨라짐. 검색을 많이 하면 바이너리면 좋지
• but, 그러려면 일단 정렬이 되어 있어야 함. 정렬과 항목 추가에 시간이 더 들어가기 때문에, 트레이드오프 수준을 잘 봐야 함.