검색과 키
검색조건
국적이 한국인 사람을 찾습니다.
나이가 21세 이상 27세 미만인 사람을 찾슷ㅂ니다.
이름에 '민' 자가 들어간 사람을 찾습니다.
이러한 검색 조건에서 주목하는 항목을 key 라고 합니다.
여기서 국적으로 검색하는 경우 국적이 key, 나이로 검색하면 나이가 key 입니다.
대부분의 key는 데이터의 일부입니다. 데0이터가 간단한 정숫값이나 문자열이면 데이터값이 그대로 key값이 될 수 있습니다.
- 국적 : 키값과 일치하도록 지정합니다.
- 나이 : 키값의 구간을 지정합니다.
- 문자 : 키값에 가깝도록 지정합니다.
검색에서는 이러한 조건을 하나만 지정할 수도 있고 논리곱, 논리합을 사용해서 지정할 수도 있습니다.
검색의 종류
검색에는 3가지의 종류가 있습니다.
- 배열검색
- 연결 리스트 검색
- 이진 검색 트리 검색
우선 배열 검색 부터 차근 차근 해 나가가려고 한다.
배열검색의 종류
- 선형검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행합니다.
- 이진검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행합니다.
- 해시법 : 추가 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행합니다.
- 체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법입니다.
- 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시 하는 방법입니다.
선형검색(Inner search)
배열에서 가장 기본적인 알고리즘은 선형 검색 입니다.
직선모양으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때 까지 맨 앞부터 스캔하여 검색하는 알고리즘 입니다.
사진에서 보이듯이 앞에서 부터 차근 차근 검색하는 방법입니다. 그래서 순차검색 이라고도 합니다.
그래서 선형검색의 종료 조건은
- 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 --> 검색 실패
- 검색할 값과 같은 원소를 찾는 경우 --> 검색 성공
선형 검색을 위한 코드를 보면
보초법(sentinel method)
선형검색하는 방법 중 한 가지 입니다. 위에 있듯이 선형 검색은 반복할 때 마다 2가지 종료조건을 검색합니다.
- 원하는 값이 있는가(n, 평균 n/2)
- 배열안에 값이 없는 경우(n +1 회)
이 두 가지를 반복하게 되는데 각 요소를 검사 할때 마다 이 종료조건 2가지를 검사하는 비용을 무시할 수가 없습니다. 그래서 나온게 보초법(sentinel method)
임의의 값을 배열의 맨 끝에 추가로 추가(보초를 세워놓고) 임의의 값을 찾아가는 검색을 진행 하는 과중에 내가 찾고자 하는 값을 찾는 과정입니다. 임의의 값을 찾게되면 검색 실패 가 됩니다.
그래서 선형검색의 종료조건 중
- 원하는 값이 있는가?
- 배열 안에 앖이 없는 경우 -> 이 조건이 사라지게 된다.
javascript 선형 탐색
이진 검색(binary search)
우선 이진 검색에서 선결되어져야 하는 부분은 데이터가 정렬이 되어 있어야 합니다.
이진 검색은 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율 적으로 검색할 수 있는 알고리즘 입니다.
1. 찾고자 하는 값이 8 인 경우 배열의 중값의 값을 기준값으로 정합니다.
2. 찾고자 하는 값이 기준값 보다 큰 경우 기준값을 시작으로 탐색을 합니다.
3. 찾고자 하는 값이 기준값 보다 작은 경우 기준값을 끝나는 지점으로 해서 다시 탐색을 실시합니다.
이 단계를 반복해서 원하는 값을 구하는 방법을 이진 검색이라고 합니다.
이진 검색의 종료조건
- 기준값과 찾고자 하는 값이 일치하는 경우
- 검색 범위가 더이상 없는 경우
javascript 이진검색
https://velog.io/@yujo/JS%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89Binary-Search
