이진 검색(탐색) (파이썬)

 

 

 

 

이진 검색(탐색)

---

 

 

 

Binary Search(이진 검색)

 

이진 탐색은 데이터가 정렬되어 있는 배열에서 찾고자 하는 수를 찾아내는 방법이다.

데이터가 정렬되어 있는 배열을 data라고 정하고 찾고자 하는 수를 target이라고 하자.

배열의 중간 인덱스를 mid로 정한다.

찾고자 하는 수(target)가 배열의 중간값(data[mid])보다 크다면 우측 데이터 대상으로,

찾고자 하는 수(target)가 배열의 중간값(data[mid])보다 작다면 좌측 데이터 대상으로 탐색을 한다.

찾고자 하는 수가 어디에 있냐에 따라 start와 end의 위치를 변경해준다.

이러한 방법을 반복하여 찾고자 하는 수를 찾을 때까지 반복해준다.

 

 

정리하면 이렇게 된다.

→ target : 찾고자 하는 값

→ data : 오름차순으로 정렬된 배열(list)

→ start : data의 처음 값 인덱스

→ end : data의 마지막 값 인덱스

→ mid : start, end의 중간 인덱스

 

 

 

이진 탐색을 쓰는 이유

 

일반 탐색은 처음부터 탐색하기 때문에 시간복잡도(Time Complexity)가 O(n)이다.

ex) 배열의 길이가 10000개라면 worstcase로 O(10000), 즉 10000번의 시간이 걸린다.

 

이진 탐색은 계속 반(N/2)씩 줄여 나가는 알고리즘이기 때문에 시간 복잡도(Time Complexity)는 O(logN)이다.

ex) 배열의 길이가 10000개라면 O(log10000)이므로 13.xx번, 즉 14번 안에는 무조건 찾는다는 알고리즘이다.

 

 

 

정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다

datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')

searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1

staIdx = 0
endIdx = len(datas) - 1
midIdx = (staIdx +  endIdx) // 2
midVal = datas[midIdx]
print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')

while searchData <= datas[len(datas)-1] and searchData >= datas[0]:

    if searchData == datas[len(datas)-1]:
        searchResultIdx = len(datas)-1
        break

    if searchData > midVal:
        staIdx = midIdx
        midIdx = (staIdx +  endIdx) // 2
        midVal = datas[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midVal: {midVal}')

    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = datas[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midVal: {midVal}')

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print(f'searchResultIdx: [{searchResultIdx}]')

 

 

 

리스트를 오름차순으로 정렬한 후 ‘7’을 검색하고 위치(인덱스)를 출력하자

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]

 

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
print(f'nums: {nums}')

nums.sort()
print(f'nums: {nums}')

searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1

staIdx = 0
endIdx = len(nums) - 1
midIdx = (staIdx +  endIdx) // 2
midVal = nums[midIdx]

while searchData <= nums[len(nums)-1] and searchData >= nums[0]:

    if searchData == nums[len(nums)-1]:
        searchResultIdx = len(nums)-1
        break

    if searchData > midVal:
        staIdx = midIdx
        midIdx = (staIdx +  endIdx) // 2
        midVal = nums[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midVal: {midVal}')

    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = nums[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midVal: {midVal}')

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print(f'searchResultIdx: [{searchResultIdx}]')

nums: [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
nums: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
찾으려는 숫자 입력: 7
midIdx: 2
midVal: 5
midIdx: 3
midVal: 7
searchResultIdx: [3]