이진탐색

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 나누어 데이터를 탐색하는 방법으로, 시작점, 끝점, 중간점을 이용

순차탐색

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

특징

• 단계마다 탐색 범위를 2로 나누는 것과 동일하기 때문에 log2N에 비례한다.
• 이진탐색은 탐색범위를 절반씩 줄어든다.
• 시간복잡도 O(logN)

예시

찾고자 하는 값

4

1단계

• (인덱스) : 시작점 : 0, 끝점: 9, 중간점 4(소수점 이하 제거)
• List : [0,2,4,6,8,10,12,14,16,18]

1. List[중간점:4]의 값은 8이 된다.
2. 8의 값이 찾고자 하는 값보다 크기 때문에, 끝점이 9->3로 변경된다.

• 끝점 수식 : 중간점 - 1

2단계

• (인덱스) : 시작점 : 0, 끝점 : 3, 중간점 : 1
• List : [0,2,3,6]

1. List[중간점:1]의 값은 2가 된다.
2. 2가 찾고자 하는 값(4) 보다 작기 때문에, 시작점이 0->2 로 변경된다.

• 시작점 수식 : 중간점 + 1

3단계

• (인덱스) : 시작점 : 2, 끝점 : 3, 중간점 :2
• List : [4,6]

1. List[중간점:2]의 값은 4가 된다.
2. 4가 찾고자 하는 값 (4)와 같기 때문에 로직은 끝나게 된다.

• 찾고자 하는 값 수식 : 중간 == 찾고자 하는 값

코드

 

def binary_search(array, target, start, end):
   while start <= end:
       mid = (start+end) // 2
       if array[mid] == target:
           return mid
       elif array[mid] > target:
           end = mid-1
       else:
           start = mid+1

    retrun None


n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)

if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)
    

자주 쓰이는 Python라이브러리

• bisect_left(array,x) : 정렬된 순서를 유지하면서 배열 array에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(array, x) : 정렬된 순서를 유지하면서 배열 array에 x를 삽입할 가장 오른쪽 인덱스를 반환
  

from bisect import bisect_left, bisect_right

a= [1,2,4,4,8]
x = 4

print(bisect_left(a,x))
print(bisect_right(a,x))

[]실행결과
2
4

값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index


a = [1,2,3,3,3,3,4,4,8,9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3))

[]실행결과
2
6

활용 예시

• 파라메트릭 서치