<탐색 알고리즘>

💡 내용

순차탐색
이진탐색
보간탐색
속도 비교

탐색 알고리즘

: 리스트/배열 내에서 특정 원소를 탐색하는 방법

순차 탐색

가장 기본적인 탐색 알고리즘
주어진 데이터를 찾기 위해 처음부터 하나씩 차례로 확인
시간복잡도: O(n)
단점 : 데이터가 큰 경우에는 적합하지 않음
장점 : 데이터가 작거나 중간 정도는 적당 / 미리 정렬 필요 X

L=[9,8,1,2,7,3,6,4,5]

def LinearSearch(L, n):
    for i in range(0, len(L)):
        if L[i] == n:
            return i
    return -1

print(LinearSearch(L, 3))

Binary Search (이진 탐색)

배열 내부 데이터가 정렬되어 있어야만 사용 가능
배열 크기 작으면 효율적이지 않음
각 단계에서 배열의 반을 제거하면서 찾는 알고리즘
시간복잡도: O(logn) - 정렬 되었을 때
배열의 정 가운데에서 시작, 타겟 값이 가운데 값보다 큰지 작은지 확인

L=[]
for i in range(0,50):
    L.append(i)

def BinSearch(L,n):
    start = 0
    end = len(L)-1
    while (start<=end):
        middle = (start+end)>>1
        if L[middle] < n:
            start = middle+1
        elif L[middle]>n:
            end = middle-1
        else:
            return middle
    return -1

Interpolation Search (보간 탐색)

이진 탐색의 최적화 (mid 대신 x로 대체)
균등하게 분포된 데이터에 대해서 찾고자 하는 값이 어디에 있는지 추측
- 평균 시간 복잡도 : O(log(logn))
- 최악 시간 복잡도 : O(n)
방법
- Idea : 균등하게 분포되어 있으므로 전체 데이터에서 6의 위치 추측

def interSearch(L,n):
    low = 0
    high = len(L)-1
    while (n>=L[low] and n<=L[high] and low<=high):
        x = low + (high-low)*(n-L[low])/(L[high]-L[low])
        x = int(x)
        if L[x]==n:
            return x
        elif L[x] <n:
            low = x+1
        else:
            high = x-1
    return -1

print("\\n======보간탐색======")
print("InterpolationSearch find 45 : ",interSearch(L,45))
print("InterpolationSearch find 60 : ",interSearch(L,60))

알고리즘 속도 비교

n의 크기를 변화하면서 linear search / binary search 검색 비교
- linear search : 정렬되지 않은 데이터
- binary search : 정렬된 데이터

def rand_list(n):
    cnt =0
    L=[]
    while cnt<n:
        a = random.randrange(0, n)
        if a not in L:
            L.append(a)
            cnt=cnt+1
    return L
def sortedlist(n):
    L=[]
    for i in range(0, n):
        L.append(n)
    return L

# Linear search vs Binary search
Ltime = 0
Btime = 0
print("\\n======속도비교======\\n")
for i in range(2, 100, 5): # 리스트 길이 설정
    print("data length : ",i)
    L = rand_list(i)
    L2 = sortedlist(i)
    Ltime = 0
    Btime = 0
    for j in range(0, 100):
        n = random.randrange(0, i)
        
        start = time.time()
        LinearSearch(L,n)
        end = time.time()
        Ltime = Ltime + (end-start)
        
        start = time.time()
        BinSearch(L2,n)
        end = time.time()
        Btime = Btime + (end-start)

    print(f"Linear search : {Ltime:.5f} sec")
    print(f"Binary search : {Btime:.5f} sec")

정렬되지 않은 데이터 n에 대해

## 정렬되지 않은 데이터 n에 대해
# msort 필요
def merge(L, R, B):
	nleft = len(L)
	nright = len(R)
	l=0
	r=0
	i=0
	while l<nleft and r<nright:
		if L[l]< R[r]:
			B[i] = L[l]
			i = i+1
			l = l+1
		else:
			B[i] = R[r]
			r=r+1
			i=i+1
	while l<nleft:
		B[i] = L[l]
		i=i+1
		l=l+1
	while r<nright:
		B[i] = R[r]
		i=i+1
		r=r+1

def msort(B):
	nlen = len(B)
	if nlen <=1:
		return B
	middle = nlen>>1
	L = B[:middle]
	R = B[middle:]

	msort(L)
	msort(R)
	merge(L, R, B)
	return B

print("\\n======정렬 X인 데이터======")
# 실질적인 시간 측정 부분
L=rand_list(1000)
for j in range(0, 1000):
    n = random.randrange(0, 1000)
    start = time.time()
    LinearSearch(L,n)
    end = time.time()
    Ltime = Ltime + (end-start)
    #sort
    start = time.time()
    L2=msort(L)
    BinSearch(L2,n)
    end = time.time()
    Btime = Btime + (end-start)

print(f"Linear search : {Ltime:.5f} sec")
print(f"Binary search : {Btime:.5f} sec") 

L=rand_list(10000)
start = time.time()
L2=msort(L)
end = time.time()
Btime = Btime + (end-start)
for j in range(0, 1000):
    n = random.randrange(0, 10000)
    start = time.time()
    LinearSearch(L,n)
    end = time.time()
    Ltime = Ltime + (end-start)
    start = time.time()
    BinSearch(L2,n)
    end = time.time()
    Btime = Btime + (end-start)
print(f"Linear search : {Ltime:.5f} sec")
print(f"Binary search : {Btime:.5f} sec")