선형탐색과 이진탐색
만약 리스트로 나열된 숫자데이터가 존재한다고 하자!!
[1, 3, 5, 6, 45, 65, 76, 88, 100]
여기서 88을 찾는다고 하면 어떻게 해야 될까?
컴퓨터라면 처음부터 하나씩 비교해가면서 88인지 확인을 할 것이다.
1 == 88 아니다.
3 == 88 아니다.
.
.
.
88 == 88 맞다.
이런식으로 빠르게 값을 비교해서 해당 값이 맞는지 확인한다.
코드로 구현 한다면 for문을 이용해서 모든 값을 돌면서 확인 한다.
이런 방법을 선형탐색이라고 한다.
선형탐색은 장점은 로직 구현이 간단하다는 것이다.
nums = [-1,0,3,5,9,12,15,16,18,20,39,40]
target = 5
def serch(nums, target):
idx = 0
for i in nums:
if i == target:
return idx
else:
idx = idx +1
if idx == len(nums):
return -1
result = serch(nums, target)
하지만 단점은 리스트에 1000000값이 있고, 타겟 값이 인덱스 999999에 있다면 반복문을 돌리면 999999째에 원하는 타겟 값을 찾을 수있다는 점이다.
다시 리스트를 보자!!!
이번에는 이진탐색을 이용해서 타겟 찾아보자.
[1, 3, 5, 6, 45, 65, 76, 88, 100]
여기서 다시 88을 찾는다고 가정하자.
이진탐색을 사용하면 먼저 중간에 리스트의 중간에 해당하는 값을 찾는다.
그리고 그값이 해당 타겟인지 확인한다.
45 == 88 아니다.
88은 45보다 크니까 오른쪽에 위치한다.
그렇기 때문에 다시 범위를 좁혀서 중간을 확인한다.
[65, 76, 88, 100]
76 == 88 아니다.
[88, 100]
88 == 88 맞다.
이렇게 타겟 값을 찾을 수 있다.
이진탐색은 반드시 값이 정렬되어 있어야 한다는 전제가 있다. 그렇지 않으면 중간값을 비교후 값이 왼쪽에 있는지 오른쪽에 있는지 확인을 할 수가 없다.
nums = [-1,0,3,5,9,12,15,16,18,20,39,40]
target = 0
def search(nums, target):
#초기 구간을 설정하는 코드
min_idx = 0
max_idx = len(nums)-1
#타겟이 없을 경우를 위한 count 변수
count = 0
while nums[int((min_idx+max_idx)/2)] != target:
if nums[int((min_idx+max_idx)/2)] < target:
# 타겟이 오른쪽에 있으므로 최소값으로 중간 인덱스보다 1크게 설정
min_idx = int((min_idx+max_idx)/2) +1
else:
# 타겟이 왼쪽에 있으므로 최대값으로 중간 인덱스보다 1작게 설정
max_idx = int((min_idx+max_idx)/2) -1
#반복문을 한 번 돌때 마다 count를 증가
count = count+1
# count를 타겟 유무 확인 코드
if count > len(nums)/2:
return -1
return int((min_idx+max_idx)/2)
result = search(nums, target)
print(result)