반드시 알아야하는 알고리즘 top 8 - 2. 이진 탐색

반드시 알아야 하는 알고리즘 top 8

• 재귀 알고리즘 

• 이진 탐색 

• 순차 탐색

• 버블 정렬

• 삽입 정렬

• 탐욕 알고리즘

• 최단거리 알고리즘

• 몬테 카를로 알고리즘

이진 탐색 

• 이진 탐색이란 탐색 알고리즘 중 아주 직관적이고 간단한 알고리즘입니다. 이런 이름이 붙여진 이유는 한번 비교할 때마다 검색할 데이터의 양이 반씩 줄어드는 형태로 검색을 진행하기 때문입니다. 다음 영상을 참고하시면 구체적으로 어떻게 진행되는지 알 수 있습니다.

이진 탐색 코드 : Python 

def binary_search(data, number=0):

    mid = int(len(data)/2)

    if len(data) > 1:    

        if data[mid] > number:

            binary_search(data[:mid],number)

        elif data[mid] < number:

            binary_search(data[mid:],number)

        else:

            print(number,"True")

    else:

        print(number,data[0]==number)

    

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

binary_search(data,5)

• 이진 탐색 알고리즘을 재귀적으로 구현한 함수 입니다. 

• 처음에 data 의 길이가 1보다 큰지, 다시말해 데이터 리스트 안의 값들이 2개 이상인지 확인하는 과정을 거칩니다.

• 이후 data 리스트의 중간값을 mid 변수에 넣고 data 리스트의 중간값과 찾고자 하는 값을 비교합니다. 

• 찾고자하는 값이 중간값보다 큰 경우에는 중간값의 뒷부분을 다시 binary_search() 함수에 넣고, 찾고자하는 값이 중간값보다 작은 경우에는 중간값의 앞부분을 binary_search() 함수에 넣어 함수를 재귀호출 합니다. 혹 중간값과 찾고자하는 값이 같은 경우에는 바로 True 를 print 하는 함수입니다.

• 재귀 호출이 진행되면서 data 리스트의 개수가 1개 이하로 작아졌을 경우에는 바로 하나 남은 값과 찾고자 하는 값을 비교하여 print 합니다.

---

부족한 블로그에 방문해 주셔서 감사합니다.

잘못된 부분이나 질문이 있으시면 

댓글로 말씀해주세요.

금방 확인하고 피드백 드리겠습니다.

좋은 하루 되세요. ^^