Search algorithm(검색, 탐색 알고리즘) 2탄 - Binary search(이진검색)

 

2. Binary search (이진 검색 알고리즘)

- 리스트 안의 값들이 이미 sorted된 상태에서 실시.

1. 중앙값을 가장 먼저 확인.
2. 중앙값보다 찾는 값이 작으면, 왼쪽 파트에서 다시 탐색. 왼쪽 파트 중 중앙값 확인.
   반대로 중앙값보다 찾는 값이 크면, 오른쪽 파트에서 다시 탐색. 오른쪽 파트 중 중앙값 확인.
3. 계~속 이런 방식으로 확인해서 탐색함!

 

 

---

# 예시

 

첫인덱스 = 0, 끝인덱스 = 6

찾는값: 20

 

 

(0+6)//2 = 3  → 중간인덱스 = 3

10 < 20  → 오른쪽 파트만 남김.

 

(4+6)//2 = 5 → 중간인덱스 = 5

20 = 20 !!

인덱스 5 return됨!!

 

 

---

 

 

(그냥 제가 짠 코드라서 뭔가 오류가 있을 수도 있음을 주의해 주세요...ㅎㅎㅎ)

#버전1(by me)
from typing import List, Any
def binary(l : List, val : Any) -> int:
    start = 0
    end = len(l)-1
    while start <= end:
        mid = (start+end)//2
        if l[mid] == val:
            return mid
        elif l[mid] > val:
            end = mid-1
        else:
            start = mid+1
    return -1

 

 

 

위 코드는 우연히 중간에 원하는 값이 위치한 경우 바로 끝나는 알고리즘입니다.

가장 왼쪽 값 즉, 가장 앞에 위치한 값의 인덱스가 출력되길 원하면,

아래(버전2)와 같이 코딩을 짜야 합니다.

 

 

#버전2 (다른 코드 참고)
from typing import List, Any
def binary(L : List, val : Any) -> int:
    start = 0
    end = len(L)-1
    while start <= end:
        mid = (start+end)//2
        if L[mid] >= val:
            end = mid-1
        else:
            start = mid+1       
    if start < len(L) and L[start]==val:
        return start
    else:
        return -1

binary([1,2,9,9,10,10,15,20,21,21], 9)   >> 2

 

 

 

가장 오른쪽 값 즉, 가장 뒤에 위치한 값의 인덱스가 출력되길 원하면,

아래(버전3)와 같이 코딩을 짜야 합니다.

 

#버전3(by me)
from typing import List, Any
def binary(L : List, val : Any) -> int:
    start = 0
    end = len(L)-1
    while start <= end:
        mid = (start+end)//2
        if L[mid] <= val:
        	start = mid+1
        else:
        	end = mid-1
    if end < len(L) and L[end]==val:
        return end
    else:
        return -1

binary([1,2,7,9,9,9], 9)   >> 5