do it 자료구조와 함께 배우는 알고리즘 입문
검색 알고리즘
검색과 키
- 검색의 공통점 : 특정항목에 주목함
- 키(key) : 주목하는 항목
배열에서 검색하기
- 검색과 검색 이외의 작업에 소요되는 비용을 종합적으로 평가하여 사용할 알고리즘을 선택해야 함
선형검색
선형검색
- 직선으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날때까지 앞에서부터 순서대로 요소를 검색하는 것(순차검색)
- 검색 종료 조건 :
검색할 값을 발견하지 못하고 배열의 끝을 지나는 경우
검색할 값과 같은 요소를 발견한 경우
보초법
- 선형 조건의 두가지 검색 종료 조건을 검사하는 비용을 줄이기 위한 방법
- 검색할값(key)를 보초로 배열에 마지막에 추가하는 방법
이진검색
이진검색
- 오름차순이나 내림차순으로 정렬되어 있다는 전재
- 선형검색보다 빠른 속도
- 검색할때마다 검색 범위가 절반으로 줄어드므로 평균 횟수는 log n
- 가운데 값을 기준으로 검색범위를 좁혀나가는 방법
Arrays.binarySearch
- Java에서 제공하는 이진검색 메서드
- 반환값
- 검색 성공시 : 해당 요소의 인덱스
- 검색 실패시 : -(해당 요소가 삽입될 위치)-1
- 장점
- 이진 검색 메서드를 직접 코딩할 필요가 없음
- 모든 자료형 배열에서 검색할 수 있음
복잡도
복잡도의 요소
- 시간 복잡도 : 실행에 필요한 시간을 평가한 것
- 공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
일반적인 복잡도 계산법
O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
선형 검색의 시간 복잡도
- O(n)
이진 검색의 시간 복잡도
- O(log n)
