[ Algorithm ] 선형검색( Linear Search), 이진검색(Binary Search)

선형 검색(Linear Search)

• 순차 검색(Sequential Search)이라고도 한다.
• 데이터가 모인 집합(배열, lined List)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘

• 데이터를 정렬할 필요가 없음
• 데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아지고, 하나씩 일일이 비교하기 때문에 비효율적이라는 단점이 있음
• 10개의 데이터가 있을 경우 마지막에 있는 데이터를 찾는 경우 10번의 비교가 필요하지만 100만개의 데이터가 있는경우 100만번의 비교가 필요함
• 선형검색은 linked list에서 자주 쓰임

def linear_search(sequence, key):
	for i in range(len(sequence)):
    	if sequence[i] == key:
        	return i
        return None

 

이진검색(Binary Search)

• 이진검색은 트리구조에서 자주 쓰이는 형식
• 이진검색은 데이터를 계속 반으로 나누면서 연산하기 때문에 처리속도가 매우 빠르다는 장점을 가지고 있음
• 이진검색을 하기위해서는 데이터의 집합이 반드시 정렬(sort)되어야 한다는 단점이 존재

• 배열의 중간에 있는 임의 값을 선택하여 찾고자 하는 값 x와 비교한다.  x가중간 값보다 작으면 중간 값을 기준으로좌측의 대상으로, x가 중간값보다 크면 우측을 대상으로 다시 탐색한다. 해당 값을 찾을 때까지 이 과정을 반복한다.
• 종료조건
  • 원하는 값을 찾으면 종료
  • 탐색하고자 하는 배열이 더이상 존재하지 않으면 찾고자 하는 값이 배열에 존재하지 않는다는 것으로 판단할 수 있고 탐색을 종료한다.

def binary_search(target, data):
	data.sort()
    start = 0
    end = len(data) - 1
    
    while start <= end:
    	mid = (start + end) // 2
        
        if data[mid] == tartget:
        	return mid # 함수 종료
        elif data[mid] < target:
        	start = mid + 1
        else:
        	end = mid -1
    return None

 

REFERENCE

https://andrew0409.tistory.com/143

자료구조 : 선형검색(Linear Search)와 이진 검색(Binary Search)

https://minimilab.tistory.com/44

파이썬 선형탐색(Linear Search), 이진탐색(Binary Search)

https://cjh5414.github.io/binary-search/

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제

https://wayhome25.github.io/cs/2017/04/15/cs-16/

강의노트 15-2. [탐색] 이진탐색(Binary Search) 알고리즘 · 초보몽키의 개발공부로그