Binary Search 이진 탐색 이분 탐색

 

✊✋ Binary Search  ✋✊

이진탐색, 이분탐색 

 

 

0, 1, 0, 1??? 처음 이 알고리즘을 알았을 때는 0 과 1의 알고리즘인 줄 알았다. 

그러나 그러한 개념보다는 이진 탐색은 탐색시간을 단축시키기 위한 알고리즘으로 기억하는게 옳다.

반드시 정렬을 하여 사용하는데, 개인적으로 사용을 하면서 느낀점과 기억해야 할 것을 기록하려 한다. 

 

탐색할 자료를 둘로 나누어 해당 데이터가 있을 만한 곳을 탐색하는 방법이다. 

순차 탐색에 비해서는 굉장히 효율적이고 빨라보이지만, 반드시 정렬이 되어있어햐 하며, 

경우에 따라서는 쓰기 곤란한 경우가 있다. 

 

이진 탐색의 계산복잡도는 O(logn)

순차 탐색이 O(n)이다.

 

- 연결리스트의 경우 이러한 이진 탐색은 불가능 하다. (물론 구현은 가능하다. 번거로울 뿐) 

 

기본 함수 개념 코드 (수도 코드) 

def binary_search(find, data): 
	if len(data) == 1 and data[0] != find
    	return False
    elif len(data) == 1 and daa[0] == data:
    	return True 
    
    mid = len(data)//2
    
    if data > data[mid] :
    	return binary_search(find, data[:mid] 
    else: 
    	return binary_search(find, data[mid:]
        

 

 

 

 

---

참고 사이트 

잔재미 코딩