Binary Search

• Reference
• O(logn)의 Search를 기대하는 알고리즘이다.
• Pivot을 간단히 설정하여 해당 Target value를 찾아내면된다.

1. Algorithm

• 구현은 간단하지만 반드시 알고 있어야한다.
• L은 left, R은 right 라고 가정하면 초기값은 vector 및 Array의 begin, end 값이라고 보면된다.
• Pivot을 L과 R의 중간 Idx 로 설정하여 해당 Target과 비교하며 업데이트한다.
  • pivot이 target 보다 크다 ? -> L이 pivot + 1 index로 업데이트
  • pivot이 target 보다 작다 ? -> R이 pivot - 1 index로 업데이트
  • L과 R의 인덱스가 엇갈리면 Not Exist다.

2. Implementation

#include <iostream>
#include <vector>

int binarySearch(std::vector<int> &v, auto target)
{
    int leftIdx = 0;
    int rightIdx = v.size() - 1;
    int pivotIdx;

    while (leftIdx <= rightIdx)
    {
        pivotIdx = (leftIdx + rightIdx) / 2;

        if (v[pivotIdx] == target)
        {
            return pivotIdx;
        }
        else if (v[pivotIdx] < target)
        {
            leftIdx = pivotIdx + 1;
        }
        else
        {
            rightIdx = pivotIdx - 1;
        }
    }

    return -1;
}

int main()
{
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};

    auto targetIdx = binarySearch(v, 5);

    if (targetIdx != -1)
        std::cout << "target Idx is : " << targetIdx << std::endl;
    else
        std::cout << "Not Exist" << std::endl;

    return 0;
}

target Idx is : 4