티스토리 뷰

import random
#1. sort
MAX = 10
a = []

for x in range(MAX):
    a.append(random.randrange(1,100))

print a
for x in range(MAX-1):
    for y in range(x+1,MAX):
        if a[x] > a[y]:
            a[x], a[y] = a[y], a[x]
print a

#2. binary search
MAX = 1000
a = []
# 천개의 원소가 들어가는 리스트를 만든다.
for x in range(1,MAX+1):
    a.append(random.randrange(1,1000))
# 그것들을 정렬하고...
a.sort()

# 찾을 원소를 적고...
compared = int(raw_input("1~1000 : "))

s_min = 0 #시작
s_max = MAX-1 #끝
cnt = 1 #몇번 만에 맞추는지 알아보려고...

while 1:
    s_div = (s_min+s_max)/2
    print cnt,"th serarching...",s_min,"~",s_max
    cnt += 1
    if s_div == s_min:
        print "찾을게 없구만..."
        break
    
    if compared == a[s_div]:
        print s_div,"에 위치하고 있음"
        print "a[%d] = %d"%(s_div,a[s_div])
        break
    elif compared > a[s_div]:
        s_min = s_div
    elif compared < a[s_div]:
        s_max = s_div

sort야 기본적인 비교 정렬 방식이어서, 대충 해본 것이고...
두번째 예제를 보면 sort()를 이용해서 바로 리스트들의 원소들을 sorting할 수 있다.

1000개의 랜덤 원소들을 담는 리스트에서 내가 원하는 값을 찾고, 그 위치까지 알아내는 검색인데, 이진 검색 기술을 사용하면 굉장히 빠른 속도로 찾을 수 있다는 것을 알 수 있다. 물론 자료들은 정렬이 되어 있어야 한다!!

일일히 비교해서 다 찾는 다는 것은 정말 시간 낭비인 것은 누구나 다 아는 센스~
댓글
댓글쓰기 폼