[알고리즘] 탐색 알고리즘 - 이진탐색, 순차탐색

1. 분할 정복 알고리즘과 이진 탐색

1) 분할 정복 알고리즘(Divide and Conquer)

- Divide : 문제를 하나 or 둘 이상으로 나눔
- Conquer : 나눠진 문제가 충분히 작고 해결이 가능하다면 해결하고, 그렇지 않으면 다시 나눔

2) 이진 탐색
- Divide : 리스트를 2개의 서브 리스트로 나눔
- Conquer
    - 검색할 숫자 > 중간값 : 뒷 부분의 서브 리스트에서 검색할 숫자를 찾음
    - 검색할 숫자 < 중간값 : 앞 부분의 서브 리스트에서 검색할 숫자를 찾음

 

2. 이진 탐색 코드

def binary_search(data, search):
    if len(data) == 1 and search == data[0]: # 사이즈가 1일 때, 그 때 검색할 데이터 존재할 경우
    	return True
    if len(data) == 1 and search != data[0]:
    	return False
    if len(data) == 0:
    	return False
        
    medium = len(data) // 2
    if search == data[medium]:
    	return True
    else:
    	if search > data[medium]:
        	return binary_search(data[medium:], search)
        else:
        	return binary_search(data[:medium], search)

- 최종 시간 복잡도 : O(logn)

---

3. 순차탐색

- 데이터가 담겨 있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾음

- 시간복잡도 : O(n)

def sequencial(data_list, search_data):
	for index in range(len(data_list)):
    	if data_list[index] == search_data:
        	return index
    return -1

 

출처

① 이진탐색 https://www.fun-coding.org/DS&AL4-8.html

② 순차탐색 https://www.fun-coding.org/Chapter16-seqsearch.html

③ 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online