[이진탐색 알고리즘] , [투 포인터스 알고리즘] 차이

[이분탐색 알고리즘 : https://ledgku.tistory.com/35]

[탐색 알고리즘] 이진 탐색 알고리즘(Binary Search)

[이진탐색 대표문제]
https://www.acmicpc.net/problem/1920

1920번: 수 찾기

#include <iostream>
#include <algorithm>
using namespace std;

int arr[100001];

int sol(int len, int search) {
	int start = 0;
	int end = len - 1;

	while (end - start >= 0) {
		int mid = (start + end) / 2;

		if (arr[mid] == search) {
			cout << 1 << "\n";
			return 0;
		}
		else if (arr[mid] > search) {
			end = mid - 1;
		}
		else {
			start = mid + 1;
		}
	}

	cout << 0 << "\n";
	return 0;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}
	sort(arr, arr + n);

	int m;
	cin >> m;
	for (int i = 0; i < m; ++i) {
		int tmp;
		cin >> tmp;
		sol(n, tmp);
	}
}

[투 포인터스 알고리즘 : https://naivep.tistory.com/52]

투 포인터스 알고리즘 (Two Pointers Algorithm)

투 포인터 알고리즘 - 1차원 배열에서 연속되는 값들을 이용해서(정렬X) 문제를 해결해야할 때 두 개의 포인터를 이용해 원하는 결과를 얻는 알고리즘

[투 포인터스 대표문제]
https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

#include 
using namespace std;
const int M = 10000 + 1;

int arr[M];

int main() {
	int n, s;
	cin >> n >> s;

	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}

	int l = 0;
	int r = 0;
	int sum = 0;
	int cnt = 0;
	while (l <= r && r <= n) {
		if (sum >= s) {//현재sum이 크다면 l++
			if (sum == s) {
				cnt++;
			}
			sum -= arr[l];
			l++;
		}
		else {//현재sum이 작다면 r++
			sum += arr[r];
			r++;
		}
	}

	cout << cnt << endl;
}

['이진탐색'과 '투 포인터' 차이]
01.
이진탐색은 log n을 보장하고, 투포인터는 최악의 경우 n 이라고 할 수 있습니다.

02.
이진탐색은 mid를 활용해서 매 연산마다 탐색하는 범위를 절반으로 좁혀나가는
반면에 투포인터는 양끝단에서 한칸씩 이동하면서 알맞는 값을 찾는 식으로 쓰이죠. left와 right가 중간 어디서 만날때까지 계속 탐색을 하게 될거구요.

03.
이진탐색의 경우 탐색 대상 데이터가 정렬되어있다는 가정하에 탐색을 하게 됩니다. 투 포인터는 그런 제약이 없죠. (필요할때도 있겠지만)