[자료구조] Binary search (with Recursion(재귀) pseudo code) 예제.

Binary search (이진 탐색) Example.

 

    #  주어진 정렬된 리스트 A[0...n-1]에서 값을 찾아라.

    #  A[]의 값들은 서로 다르다고 가정한다 : A[i] != A[j] (i != j)

    #  원하는 리턴값(결과)

        -  -1  :  원하는 값이 리스트 안에 존재하지 않을 때

        -  pos  :  A[pos] = value

    #  Binary search

        -  리스트가 정렬되어 있음을 이용하라.

        -  A[middle]과 value를 비교하라.

        -  if A[middle] = value, return middle // value is found.

        -  if A[middle] != value, 리스트의 반쪽중에 하나로 범위를 좁혀나가라.

 

---

Binary search. Pseudo code.

binary_search(A[0...n-1],value){                 // 리스트 A[0...n-1]에 value값이 들어가 있는가?
    left <- 0                                    // 가장 좌측
    right <- n-1                                 // 가장 우측
    while(left <= right) do{                     // value값이 없을때 while안의 조건문을 이용해서 return -1을 하게됨.
        mid <- (left + right) / 2                // mid값
        switch(compare(value, A[mid])){          // value와 A[mid]를 compare해서 case에 따라 left,right값을 바꾼다.
                                                 // 같다면 mid를 리턴.
            case '<' : right <- mid-1
            case '=' : return mid
            case '>' : left <- mid+1
        }
    }
    return -1
}
    
    

---

Recursion funcion(재귀적 함수)

 

A function that calls itself

example : n_factorial.

Factorial(n){                       // input : n (>=0), output : n!
    if (n=0) return(1)              // 종료조건 0! =1
    return (n*Factorical(n-1))      // 재귀적 호출의 결과로 Factorial(n)함수 작성.
}

---

Binary search. Pseudo code. with Recursion function.

binary_search(A[],left,right,value){            
    mid <- (left + right) / 2                
    switch(compare(value, A[mid])){         
        case '<' : pos <- binaray_search(A[],left,mid-1,value)  // 재귀함수를 이용해 훨씬 깔끔하게 표현가능.
        case '=' : pos <- mid
        case '>' : pos <- binaray_search(A[],mid+1,right,value) // 재귀함수를 사용하면 loop을 돌리지 않아도됨.
    }
    return pos
}

---

 

 

 

 

출처

CAU DBLab

https://intellipaat.com/blog/tutorial/python-tutorial/data-structures-with-python-cheat-sheet/