이진검색

[알고리즘] 검색 Search - 순차 검색, 이진 검색 (자바/Java)

목차 검색 자료에서 원하는 항목을 찾는 작업 종류 순차 검색 이진 검색 인덱싱 순차 검색 일렬로 되어 있는 자료를 순서대로 검색 장점: 배열, 연결 리스트 등에서 유용 단점: 자료의 크기가 큰 경우에 비효율적 정렬X 첫 번째 원소부터 마지막 원소까지 키 값이 같은 원소가 있는지 검색 동일한 원소를 찾으면 검색을 중지하고 그 인덱스를 반환 마지막 원소까지 키를 찾지 못하면 실패 시간 복잡도: O(n) 정렬O 첫 번째 원소부터 키 값보다 큰 원소가 나올 때까지 검색 동일한 원소를 찾으면 반환, 키 값보다 큰 원소가 나왔는데 찾지 못하면 검색 실패 시간 복잡도: O(n) 그러나 정렬되지 않았을 때보다 평균 비교 횟수가 절반으로 줄어든다. 이진 검색 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위..