순환 알고리즘의 설계

설계 조건에 대해 말해보겠다. 

 

순환 알고리즘을 만들기에 앞서 

이전에 배운 조건문을 기억하는가? 

 

1. 적어도 하나의 Base Case를 통해 무한루프되지 않고 종료되는 Case가 있어야한다. 

결과적으로 모든 Case는 Base Case로 수렴해야한다. 

 

2. 암시적 매개변수를 명시적 매개변수로 바꿔야한다. 

 

 

이 함수의 미션은 data[0]에서 data[n-1] 사이에 target 을 검색하는 것이다.

하지만 검색 구간의 시작 인덱스 0 은 보통 생략한다.

즉 암시적 매개변수다. 

def search(dataA,target):
    for i in range(len(dataA)):
        if dataA[i] == target:
            return i
print(search([1,2,3],3))

---

이 함수의 목적은  data[begin] 에서 data[end] 사이에서 target을 검색한다.

즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다. 

이 함수를 search(data,0,n-1)로 호출한다면 앞 페이지의 함수와 동일한 일을 한다. 

 

def search(dataA,begin,end,target):
    if begin>end:
        return -1
    elif target == dataA[begin]:
        return begin
    else:
        return search(dataA,begin+1,end,target)
print(search([1,2,3],0,2,3))

 

++ 

재귀를 통해 명시적매개변수를 삽입하여 이진탐색을 구현

def BinarySearch(dataA,begin,end,target):
    if begin>end:
        return -1
    else:
        mid = (begin + end ) // 2
        if dataA[mid] == target:
            return mid
        elif dataA[mid] > target:
            BinarySearch(dataA,begin,mid-1,target)
        else:
            BinarySearch(dataA,mid+1,end,target)
print(BinarySearch([1,2,3,4,5,6],0,6,4))

여기서 잠깐 이진탐색을 모른다면 ?

아래링크를 참고하자

이미지 참고 ) https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89