[Algorithm] Binary search -recursion, iteration

Binary search

Code implementation

1. Recursion

#include <iostream>
#include <vector>
//using namespace std;

class BSException: public std::runtime_error{
    public:
        // explicit: prevent automatic type conversion 
        // constructor will only be called if the correct type of argument (const char*) is explicitly provided
        explicit BSException(const char* message): std::runtime_error(message){}
};

int binarySearch(const std::vector<int>& array, int target, int lower, int upper)
{
    int center, range;
    range = upper - lower;

    if (range <0){throw BSException("Limits reversed");}
    else if(range==0 && array[lower]!=target){throw BSException("Element not in array.");}
    if (array[lower] > array[upper]) {throw BSException("Array not sorted");}

    center = (range/2) + lower;

    if (target==array[center]){return center;}
    else if (target<array[center]){binarySearch(array, target, lower, center-1);}
    else{binarySearch(array, target, center+1, upper);}
}

/*
* std::vector: c++ 동적 배열! -> 동적으로 메모리를 할당해준다!
*/
int bsearch(const std::vector<int>& array, int target)
{
    return binarySearch(array, target, 0, array.size()-1);
}

2. Iterative method

int binarySearch(const std::vector<int>& array, int target, int lower, int upper)
{
    int range, center;
    while (true){
        range = upper - lower;
        if (range < 0){throw BSException("limits reversed!");}
        else if (range==0 && array[lower]!=target){throw BSException("Element not in array.");}
        if (array[lower]>array[upper]){throw BSException("array is not sorted");}
        
        center = range/2 + lower;

        if (array[center]==target){return center;}
        else if (target>array[center]){lower=center+1;}
        else {upper=center-1;}
    }

}

Test

int main(){

    std::vector<int> sortedArray = {1,4,6,10, 13,15,16, 19};

    // first trial
    int target= 6;
    try{
        int result=bsearch(sortedArray, target);
        std::cout << "Element found at index: " << result << std::endl;
    }catch(const BSException& e){
        std::cout << "Error: " << e.what() << std::endl;
    }
    // 2nd trial
    target = 4;
    try{
        int result=bsearch(sortedArray, target);
        std::cout << "Element found at index: " << result << std::endl;
    }catch(const BSException& e){
        std::cout << "Error: " << e.what() << std::endl;
    }
    return 0;
}

Time complexity

• if the array is already sorted, $O(logn)$