221024 Array 검색(Search)

검색(Search)
1.순차검색:데이터를 앞에서부터 순서대로 탐색
나쁜 방법. 찾으려는 위치에 따라 너무 오래 걸린다.

 

2.제어검색:정렬한 후 검색
-⑴ Binary Search(미분 검색) : 중앙값과 비교
작으면 왼쪽가서 찾고, 크면 오른쪽가서 찾는 방식. 가운데 가고, 다시 왼쪽/오른쪽 가운데 가고...반복
한번만 하면 순차가 빠름. 여러번 할 때 Binary Search가 빠름
-⑵ Fibonacci Search
순차검색의 방법을 조금 다르게
첫번째하고 두번째는 무조건 1. 세번째부터는 앞의 두개의 합.
이 수열은 금융의 기본. 앞의 몇개를 가져오는 건 정할 수 있음. 최근 2주, 최근 3달 등이 이런 방식.
-⑶ 보간 검색 : 검색 위치를 계산
(검색값-최솟값/최대값-최솟값)*데이터 개수==>비율을 계산하는 것.
{1, 2, 3, 4, 5, 6, 7}이면 7번째에 가서 찾으라고 함.
but 치명적인 단점->간격이 달라지면 제대로 찾지 못한다.
{1, 2, 3, 4, 5, 6, 10000}(10000-아웃라이어Outlier 데이터가 있음)같은 경우 앞의 식을 계산하면 앞에 가서 찾게 됨. 
-★★★⑷ 트리검색
데이터를 만들 때 크면 오른쪽으로, 작으면 왼쪽으로. 맨 위는 하나.
데이터에 따라 좌 우 비중이 안맞을 수도 있음
-⑸ Block Search : Block은 정렬이 되어 있지만 Block 내부는 정렬하지 않음
ex)블록 10으로 시작-11 19 14
20-27 21 25
30-31 34 39

 

3.해싱 : 해시함수 이용
이전의 방법은 데이터에 따라 검색시간이 다름.
ex) mod 5=>5로 나눈 나머지에 따라 값들을 나눔. 
{21 14 13 10 2}
검색을 할 때도 원하는 값을 5로 나누고, 맞는 자리로 감.
이러면 모든 데이터의 검색 시간이 같아진다.
스마트폰의 음악 검색도 이런 방법. 
#해싱은 데이터를 구별하기 위해 계산을 한다#