[20.08.26]binary search 이진탐색알고리즘

정렬 되어있는 데이터를 검색할 때,for문으로 찾는 것보다 Binary Search로 더 빨리 원하는 값을 찾을 수 있습니다.
(주의: Binary Search와 Binary Search Tree를 헷갈리지마세요!)

 

1. sort 정렬 후 mid 중간값 찾기

2. 배열의 처음인덱스 start, 마지막인덱스 end

3. target이 mid보다 작으면 end를 mid-1/ 크면 start를 mid+1

4. start가 end와 만나거나 넘으면 target없음

#include<iostream>
#include<vector>

using namespace std;

int target;
vector<int>vect = { 1,2,5,33,44,63,34,99 };

int bsearch(int start, int end, int target) {
    while (1) {
        int mid = (start + end) / 2;
        if (vect[mid] == target)return 1;
        if (start > end)return -1;
        if (target > vect[mid]) start = mid + 1;
        else end = mid - 1;
    }
}

int main() {

    cin >> target;
    int ret = bsearch(0, 7, target);
    if (ret == 1) cout << "찾음";
    else cout << "없음";

    return 0;
}

- 배터리양 확인하기

#include<iostream>
#include<vector>

using namespace std;
string power = "####______";

int bsearch(int start, int end)
{
    int Max = -1;
    while (1)
    {
        int mid = (start + end) / 2;
        if (start > end)break;
        if (power[mid] == '#')
        {
            if (Max < mid)Max = mid;
            start = mid + 1;
        }
        else end = mid - 1;
    }
    return Max;
}

int main()
{
    int ret = bsearch(0, power.size() - 1);
    cout << (ret + 1) * 10 << "%";
    return 0;
}