-
탐색알고리즘
a. 선형 탐색 알고리즘
1. 정렬되지 않은 초기 리스트를 처음부터 끝까지 차례로 검사.
2. 리스트에 원하는 요소가 있는 경우 평균적으로 (n+1)/2의 비교를 요소를 찾아 낼 수 있지만 요소가 없을 경우 n+1 번의 비교로 끝나게 됨.
3. 시간 복잡도 : O(n)
b. 이진 탐색 알고리즘
1. 정렬된 리스트에 적용하기 좋음
2. 리스트에 원하는 요소가 존재하지 않는 경우, 리스트의 요소를 1/2씩 줄여가므로 최악의 경우 lgn번의 비교 필요.
3. 시간복잡도 : O(lgn)
a. 선형 탐색 알고리즘
순서대로 하나씩 찾기
b. 이진 탐색 알고리즘
전제
정렬된 배열에서 사용 가능한 알고리즘
1. 배열 전체의 중간값을 target 값과 비교
2. 중간값이 target 값보다 크면 왼쪽 부분만 선택
3. 왼쪽부분의 중간값을 다시 target과 비교
