• 계산 문제를 해결하기 위해 데이터를 변환하는 방법도 프로그램 유용성 결정에 중요한 요소다. 주어진 문제가 있을 때, 데이터에 대한 정확한 정의와 변환 순서는 일련의 명령에 의해 결정되며 이를 알고리즘이라고 한다.

이진 검색

• Linear search : 시퀀스 전체 원소를 방문하면서 해당 원소가 N과 같은지 확인하는 방법

bool linear_search(int N, std::vector<int>& sequence)
{
	for (auto i : sequence)
    {
    	if( i == N)
        	return true;
	}
    
    return false;
}

• 장점 : 정렬 여부와 상관 없이 항상 잘 동작한다.
• 그러나 효율적이지 않고, 대부분 주어진 배열이 정렬되어있음을 활용하기 어렵다.
• 시퀀스가 정렬되어있다는 것을 활용한다면 ?
  • 전체 시퀀스 범위 range로 설정
  • 현재 range 가운데 원소 M이라하고, N과 M 비교
  • if M == N, 검색 성공, 검색 중단
  • else, range 수정
    • if N < M, N이 M의 왼쪽에 있다고 예상되므로 range에서 M 오른쪽 모든 원소 제거
    • else if N > M, M 왼쪽 원소 제거
  • range에 한 개 보다 많은 원소가 남아있으면 2번째로 이동
  • 그렇지 않으면 N이 시퀀스에 존재하지 않은 것이므로 검색 종료

#include <vector>
#include <chrono>
#include <random>
#include <algorithm>

bool binary_search(int N, std::vector<int>& S)
{
	auto first = S.begin();
    auto last = S.end();
    
    while (true)
    {
    	auto range_length = std::distance(first, last);
        auto mid_element_index = first + std::floor(range_length / 2);
        auto mid_element = *(first + mid_element_index);
        
        if (mid_element == N)
        	return true;
		else if (mid_element > N)
        	std::advance(last, -mid_element_index);
		if (mid_element < N)
        	std::advance(first, mid_element_index);
            
		if (range_length == 1)
        	return false;
	}
}

• std::distance(), std::advance()를 사용해 반복자를 활용한 코딩 방식은 데이터 타입에 영향을 받지 않으면서 부정확한 배열 인덱스 사용 위험이 줄어들어 권장하는 방법이다.
  • 데이터 타입과 알고리즘 로직을 분리하는 것이 모던 C++에서 재사용 가능한 코드를 작성하는 기본 방침이다.