이분 탐색
값을 찾을때 배열을 절반씩을 없애가며 찾아가는 탐색법 단, 배열은 정렬되어 있어야한다.
선형 탐색
탐색법중 선형 탐색과 이진 탐색 등 여러가지가 존재합니다.
선형 탐색이란 주어진 배열 또는 리스트를 처음부터 끝까지 순서대로 탐색을 하는 방식을말하는데요
N은 배열의 길이
처음부터 순서대로 찾는방법이라 최선의 수일때는 O(1)이 나올 수 있지만 최악일 경우에는 O(N)이 될 수 있습니다. 왜냐하면 선형탐색에서 최적일 경우에는 탐색 방향이 앞에서 뒤로 갈때 찾는 수가 배열 맨앞에 있는 경우에 한번에 찾을 수 있지만
만약, 찾는 수가 배열의 맨 뒤에 존재하게 된다면 배열을 처음부터 끝까지 전부 탐색을 해야하기때문에 O(N)이됩니다.
# 선형 탐색
L = [1,2,3,4,5]
x = 5 # 찾고자하는 숫자
for i in range(len(L)):
if L[i] == x:
print(i)
break
하지만 이진 탐색은 주어진 배열을 반씩 잘라가며 탐색을합니다.
이진 탐색
이진 탐색은 선형 탐색과 달리 배열이 정렬되어있어야지 사용이 가능한 탐색법입니다. 정렬이 되어있지 않다면 사용 할 수 없다는것을 기억해야합니다.
아래의 방법은 이진 탐색으로 원하는 값이 존재하는 인덱스를 찾을려고합니다.
이진 탐색 방법
L = [1,2,3,4,5,6,7,8,9,10]
x = 7
low = 0 # 배열의 첫번째 인덱스
high = len(L)-1 # 배열의 끝 인덱스
middle = 0 # 이진탐색시 움직이며 기준이 되는 인덱스
Step 1. Low, High
x = 7
Low = 0
High = 8
| Index | LOW 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | HIGH 8 |
|---|---|---|---|---|---|---|---|---|---|
| L | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
위 처럼 주어진 배열이 존재할때 x의 값이 있는 L의 인덱스를 구하려고 한다면 선형탐색일 경우 하나씩 탐색하게 될겁니다. 하지만 이진 탐색은 low와 high 그리고 middle이라는 변수를 만들어 배열의 처음과 끝 그리고 움직이는 기준을 만들어 탐색을 진행하게 됩니다.
Step 2. Mid
x = 7
Low = 0
High = 8
Mid = 4 # (Low+High)//2
L[Mid] = 5
if L[Mid] == x :
return Mid
| Index | LOW 0 | 1 | 2 | 3 | MID 4 | 5 | 6 | 7 | HIGH 8 |
|---|---|---|---|---|---|---|---|---|---|
| L | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
주어진 Low와 High를 이용하여 배열의 중간 인덱스 Mid를 만들어야합니다. 이 Mid를 만들어서 숫자X를 찾기위해 숫자 X보다 큰 값들이나 작은 값들을 무시하여 작업을 진행할 수 있습니다. L[Mid]의 값과 X를 비교하여 찾는 X의 값이 L[Mid]와 같다면 찾고자하던 Index(Mid)를 출력하고 원하는 값이 아니라면 비교를 진행합니다.
Step 3. Mid 조절
x = 7
# before
Low = 0
High = 8
Mid = 4 # (Low+High)//2
if L[Mid] == x :
return Mid
elif L[Mid] < x:
Low = Mid + 1
else :
High = Mid - 1
# after
Low = 5
High = 8
Mid = 6 # (Low+High)//2
| Index | 0 | 1 | 2 | 3 | 4 | Low 5 | MID 6 | 7 | HIGH 8 |
|---|---|---|---|---|---|---|---|---|---|
| L | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
L[Mid]의 값이 X 의 값보다 작다면 Mid의 값에서 1을 더해 Low의 값으로 지정합니다 그렇게 되면 위의 그림과 같이 Low는 5가 되며 High는 기존대로 8, Mid는 Low와 High의 값 중간 6이 됩니다.
L[Mid]의 값은 7이 나오며 찾고자 하는 값과 일치합니다. 그럼 Mid를 출력하거나 리턴해주면 이진 탐색이 끝나게 됩니다.
위 방법은 간단히 이진탐색의 방법을 소개하기 위함입니다. 다른 값을 찾기 위해서는 어떻게 동작하는지 한번 찾아보시길 바랍니다.
코드
x = 7
L = [1,2,3,4,5,6,7,8]
idx = -1
low = 0
high = len(L)-1
while idx == -1 :
mid = (low+high)//2
if low > high:
print("찾고자하는 값이 없습니다.")
break
if L[mid] == x:
idx = mid
break
elif L[mid] > x:
high = mid -1
else :
low = mid + 1
백준
수 찾기 1920
x = int(input())
L = list(map(int, input().split()))
M = int(input())
CM = list(map(int,input().split()))
L.sort()
for i in range(len(CM)):
x=CM[i]
low = 0
high = len(L)-1
answer=-1
while answer == -1 :
mid = (low+high)//2
if low > high:
answer=0
if L[mid] == x:
answer = 1
elif L[mid] >x:
high = mid-1
else:
low = mid+1
print(answer)
