[ALGORITHM] 순차탐색 / 이진탐색

순차탐색 (Sequential Search)

• 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미
• 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법
• 순차적으로 탐색하기 때문에 최악의 경우 리스트 길이가 n일 경우, n번 비교해야해서 시간복잡도가 O(n) 

---

이진탐색 (Binary Search)

https://www.interviewbit.com/courses/programming/topics/binary-search/ 참고

• 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 (대상 리스트가 정렬이 되어 있어야함)
• 이진탐색은 분할정복 알고리즘을 활용하여 사용 
• Divide : 리스트를 두개의 서브 리스트로 나눔
• Conquer : 검색대상 > 중간값이면, 뒷 부분 서브리스트에서 검색대상 찾음, 검색대상 < 중간값이면, 앞 부분 서브리스트에서 찾음
• n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교연산 k회를 진행, 시간복잡도가 log2n 

---

이진탐색은 기본이라 까먹지 말아야함