이진 탐색, 이분 탐색 (Binary serach) 재귀

* 이진 탐색 (Binary serach) 개념

 

탐색 알고리즘 중에 가장 기본적인 알고리즘중 하나이다. 순차탐색(linear search)은 첫번째 요소부터 순서대로 찾을 대상이 나올때까지 검색해 나간다. 이진 탐색은 필요 없는 부분을 배제하며 검색 범위를 줄이면서 진행하는 탐색.

 

 

처음 이진탐색의 개념을 읽고, 생각나는것은 소주뚜껑으로 하던 UP-DOWN 게임이었다. 

소주뚜껑에는 1 ~ 50까지의 숫자가 있는데, 자연스럽게 숫자를 맞출 확률을 높이기 위해서 중간값을 골라가며 범위를

줄여나갔다.

예를들어 맞추는 사람이 25를 외치면, 출제자는 UP 이나 Down을 말하여 범위를 말해준다.

탐색범위 : 1 ~ 50

만약 UP을 말해주었다면 다음 순서때는 1~25까지의 범위는 탐색할 필요가 없는셈이 된다.

1차 시도 후 탐색범위 : 26  ~  50

다음으로 2차 시도때, 40을 외쳤고 출제자는 DOWN을 외쳤다면 다음 탐색범위는

2차 시도 후 탐색범위 : 26  ~  39

이런식으로 탐색 범위가 점차 줄어든다.

 

---

* 이진탐색의 코드 구현

 

• 시간복잡도 BigO : O(log N)
• 전제조건 : 반드시 정렬된 자료여야 한다. 무작위 순서라면 이진탐색을 사용할 수 없다.
• 이진탐색은 재귀(Recursive)적으로도 구현 가능하다. 같은 연산의 반복이기때문에..

(bigocheatsheet.com 의 차트에 따르면 이진탐색은 Excellent한 효율이다.)

 

• 탐색할 대상(배열) array
• 탐색 범위의 시작과 끝을 나타내는 start , end 혹은 left , right
• 탐색 범위의 중간값인 mid
• 탐색 목표인 target

이진탐색의 구현

target = 15

arr = [i for i in range(100)]
arr.sort()  # 사실 없어도 된다. for문으로 arr를 만들어서 이미 정렬된 상태라서
print(arr)
start = 0 
end = len(arr) - 1

cnt = 0
while start <= end:
    cnt +=1

    mid = (start + end) // 2
    if arr[mid] == target:
        print("%d차 시도 ,탐색 완료 !! 인덱스 번호 :%d" %(cnt, mid))
        break
    elif arr[mid] > target:
        end = mid - 1
        print("%d차 시도 :"%cnt, start,end)
    else: 
        start = mid +1
        print("%d차 시도 :"%cnt, start,end)

 

 

이진탐색 재귀적 구현

 

def binarySearch(arr, start, end, target):
    global cnt
    mid = (start + end)//2
    mid_value = arr[mid]
    cnt += 1
    if target == mid_value:
        print("%d차 시도 , 탐색 완료 !! 인덱스 번호:%d"%(cnt, mid+1))
        
    elif mid > target:
        end = mid-1
        print("%d차 시도 :"%cnt,start,end)
        binarySearch(arr, start, end, target)
        
    elif mid < target:
        start = mid +1
        print("%d차 시도  :"%cnt, start, end)
        binarySearch(arr, start, end, target)
        
    else:
        return False



arr = [i for i in range(100)]
arr.sort()
target = 15
start = 0
end = len(arr) -1 
cnt = 0
binarySearch(arr, start, end, target)

 

 

 

 

이진 탐색 구현, 재귀적 구현의 결과값 (같음)

*결과값 (출력 내용)

1차 시도 : 0 48
2차 시도 : 0 23
3차 시도  : 12 23
4차 시도 : 12 16
5차 시도  : 15 16
6차 시도 , 탐색 완료 !! 인덱스 번호:16