키리Kirri's IT노트

: 데이터가 키 값으로 이미 정렬(sort)되어 있을 때, 선형 검색보다 빠르게 검색 가능 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 ・이진 검색 알고리즘의 종료 조건 ① a[pc]와 key가 일치하는 경우(검색 성공): 대략 ⌈log(n-1)⌉회 비교 ② 검색 범위가 더 이상 없는 경우(검색 실패): ⌈log(n+1)⌉회 비교 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 static int binSearch(int[] a, int n, int key) { int pl = 0; int pr = n - 1; do { int pc = (pl + pr) / 2; // 중앙 요소의 인덱스 if(a[pc] == key) return pc; else if(a[..

: 배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘. 배열에서 순서대로 검색하는 유일한 방법이기도 하다. 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)라는 알고리즘이다. ・검색의 종료 조건 ① 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우(검색 실패) ② 검색할 값과 같은 요소를 발견한 경우(검색 성공) -while문 사용 1 2 3 4 5 6 7 8 9 10 11 12 static int seqSearch(int[] a, int n, int key) { int i = 0; while(true) { if(i == ..

: 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘 키: 검색을 수행할 때 주목하게 되는 특정 항목 1. 국적이 한국인 사람을 찾는다. 2. 나이가 21세 이상 27세 미만인 사람을 찾는다. 3. 찾으려는 이름과 가장 비슷한 이름의 사람을 찾는다. 1. 키 값과 일치하도록 지정(한국) 2. 키 값의 구간을 지정(21세 이상 27세 미만) 3. 키 값과 비슷하도록 지정(발음이 가장 비슷한 이름) 1. 선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색을 수행 2. 이진 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색 수행 3. 해시법: 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색 수행 - 체인법: 같은 해시 값의 데이터를 선형 리스트로 연결 - 오픈 주소법: 데이..