이진 탐색.

탐색 방법론.

1. 리스트를 정렬시킨다.

2. 처음에는 중간값으로 시작하여 중간값보다 크다 싶으면 (중간값 + 끝값)/2와 값 비교, 이런식으로 반씩 줄여나간다. 당연히 중간값보다 작다 싶으면 (처음값+중간값)/2와 값 비교, 이런식으로 진행한다.

특징.

1. 리스트가 이미 정렬되어 있어야만 한다.

2. 순차 탐색보다 빠르지만 리스트가 정렬되어 있어야 한다.

3. logN+1번 이상의 비교를 하지 않는다.

예전에 여기서 만들었었다.

# -*- encoding: cp949 -*-
import time
import random
import Queue
   
N = 10000

class Dict:
    class node:
        def __init():
            self.key = -1
    def __init__(self,max):
        self.a = [self.node() for i in range(max)]
        self.n = 0
    def search(self, search_key):
        left = 1
        right = self.n
        while right >= left:
            mid = (left + right)/2
            if self.a[mid].key == search_key: return mid
            if self.a[mid].key > search_key: right = mid -1
            else: left = mid + 1
        return -1

    def insert(self, v):
        self.n += 1
        self.a[self.n].key = v

def init(key, search_key):
    temp = [0 for i in range(N+1)]
    for i in range(1,N+1):
        key[i] = i
        search_key[i] = i
    for i in range(1,N+1):
        index = random.randint(1,65536)%N + 1
        if temp[index]==0:
            temp[index] = search_key[i]
        else:
            while temp[index] != 0:
                index = (index%N) + 1
            temp[index] = search_key[i]
    for i in range(1,N+1):
        search_key[i] = temp[i]

def main():
    d = Dict(N+1)
    key = [0 for i in range(N+1)]
    search_key = [0 for i in range(N+1)]
    init(key,search_key)
    for i in range(1,N+1):
        d.insert(key[i])
    start_time = time.time()
    for i in range(1,N+1):
        result = d.search(search_key[i])
        if result==-1 or key[result] != search_key[i]:
            print u'탐색 오류.'
    print u'이진 탐색의 실행 시간 (N = {} ): {}'.format(N,time.time()-start_time)
    print u'탐색 완료.'


if __name__=='__main__':
    main()