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

안녕하세요. 우당탕탕 개발일지입니다. 2학년 2학기 수강과목인 지능처리 알고리즘 과목에서 배운 내용을  정리하고 예제를 들어서 설명하겠습니다. 

 

• 알고리즘 특성, 개념
• 순차 탐색
• 이진 탐색

 

0. 알고리즘 특성, 개념

♦️ 알고리즘 이란?
: 문제를 해결하는 단계적 절차 또는 방법.

 

♦️  시간 복잡도 : 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현 

♦️ BigO 표기법

 

♦️  알고리즘의 일반적인 특성 

1. 정확성 
2. 수행성 :컴퓨터에서 수행 가능해야 한다. 
3. 유한성 : 일정한 시간 내에 종료되어야 한다.
4. 효율성

 

♦️알고리즘은 대부분 의사코드 형태로 표현된다.

 

1. 순차 탐색 알고리즘 

: 특정한 값을 찾기 위해서 리스트의 맨 앞에서부터 차례대로 확인하는 방법.

•  시간 복잡도 :O(n)

연습문제 :  순차탐색 알고리즘 구현하기
임의의 숫자를 찾기 위한 순차탐색 알고리즘을 설계하고, 이를 파이선 언어로 구현하라. 
- 이때, 작성하는 함수는 mySearch(a_list, n)이다. 
- a_list는 0~100 사이의 정수값을 무작위로 생성한 10 개의 값을 가진 리스트이다. 
- n은 호출 시에 a_list를 주고서, 찾아야 할 값이다. 
- 리턴되는 값은 리스트에서 찾아진 인덱스 값이다. 
- 찾는 숫자가 없는 경우에는  -1을 리턴한다.

import random

a_list=[]

for i in range(10):
    a_list.append(random.randint(0,100))

print(a_list)



def mySearch(a_list,n):
    for i in range(len(a_list)):
        if(a_list[i]==n):
            return i
        
    return -1


n=int(input("찾을 값을 입력하시오:"))


result=mySearch(a_list,n)

if result != -1:
    print(f"{n}은 {result+1}번째 존재합니다. ")
else:
    print(f"{n}는 리스트에 존재하지 않습니다.")

 

2. 이진 탐색 알고리즘

: 오름차순으로 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘.

시간 복잡도: O(log n)

연습문제: 이진탐색 알고리즘 구현하기 
->정렬된 숫자들에서 임의의 수자를 찾기 위한 이진탐색 알고리즘을 설계하고 이를 파이선 언어로 구현하라. 
이때, 정령은 내정함수 sorted()를 활용한다. 
 
- 작성하는 함수는 binarySearch(a_list, n)이다. 
- 숫자를 찾은 경우, 인덱스 값을 리턴하고, 찾지 못한 경우에는 -1을 리턴한다. 

 

1. 정렬하기(오름차순)

2. 가장 왼쪽 인덱스, 가장 오른쪽 인덱스  변수로 설정

3. 중간값 변수 설정

4. 중간 값과 찾으려는 값 비교.

• 중간 값 보다 찾으려는 값이 클 때 ->  왼쪽 인덱스변수 중값값 +1로 변경.
• (중간 값보다 왼쪽에는 찾으려는 값이 존재하지 않음)

• 중간 값이 보다 찾으려는 값이 작을 때 -> 오른쪽 인덱스 변수 중간값 -1로 변경
• (중간값보다 오른쪽에는 찾으려는 값이 존재하지 않음)

=> 중간 값이 찾는 값이 될 때까지 반복.

import random

a_list=[]
alist=[]

for i in range(10):
    alist.append(random.randint(0,100))

a_list=sorted(alist)
print(a_list)



def binarySearch(a_list,n):
    left=0
    right=len(a_list)-1
    while(left<=right):
        mid=(left+right)//2
        if(a_list[mid]==n):
            return mid
        elif(a_list[mid]>n):
            right=mid-1
        elif(a_list[mid]<n):
            left=mid+1
    return -1

    

n=int(input("찾을 값을 입력하시오:"))
result=binarySearch(a_list,n)

if result != -1:
    print(f"{n}은 {result+1}번째 존재합니다.")
else:
    print(f"{n}는 리스트에 존재하지 않습니다.")