10장. 검색과 정렬 검색 (search) - 검색은 자료 구조 내에 특정 항목을 찾는 일을 말하며, 배열이 정렬됐는지 여부에따라 두 가지 주요 기법이 있다. 선형 검색 배열의 각 항목을 한 인덱스씩 순차적으로 접근하면서 동작한다. 시간 복잡도 : O(n) 배열의 정렬 여부와는 관계없이 동작하기때문에 좋으므로 정렬되지 않은 배열을 검색하기 좋다. function linearSearch(arr, n) { for(var i = 0; i < arr.length; i++){ if (arr[i] == n) return true; } return false; } 이진 검색 (탐색) 중간 값을 확인해서 원하는 값보다 중간 값이 작은지 큰지를 확인하면서 동작한다. 시간 복잡도: O(logn) 이진 탐색은 빠르지만 배열..
cs지식/자료구조 2022. 7. 13. 16:40
10장. 검색과 정렬 검색 (search) - 검색은 자료 구조 내에 특정 항목을 찾는 일을 말하며, 배열이 정렬됐는지 여부에따라 두 가지 주요 기법이 있다. 선형 검색 배열의 각 항목을 한 인덱스씩 순차적으로 접근하면서 동작한다. 시간 복잡도 : O(n) 배열의 정렬 여부와는 관계없이 동작하기때문에 좋으므로 정렬되지 않은 배열을 검색하기 좋다. function linearSearch(arr, n) { for(var i = 0; i < arr.length; i++){ if (arr[i] == n) return true; } return false; } 이진 검색 (탐색) 중간 값을 확인해서 원하는 값보다 중간 값이 작은지 큰지를 확인하면서 동작한다. 시간 복잡도: O(logn) 이진 탐색은 빠르지만 배열..