[Algorithm] Binary Search, Two Pointer

단순 탐색 : O(N)

이진 탐색 : O(logN), 단 사전에 정렬이 되어 있어야 함.

 

- STL의 binary_search

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

int main()
{
	int arr[] = { 3, 5, 1, 2, 7, 4, 7, 3, 3, 9 };
	sort(arr, arr + 10);
	cout << binary_search(arr, arr + 11, 7);	//true
	return 0;
}

 

 

- Binary Search 구현

#include <iostream>
#include <algorithm>
using namespace std;
int arr[] = { 4, 1, 5, 3, 2, 1, 1, 6 };
int target = 3;
int binary_search(int start, int end)
{
	int mid = 0;
	while (start <= end)
	{
		mid = (start + end) / 2;
		//중앙 검사
		if (arr[mid] == target)
			return mid;

		if (arr[mid] > target)
		{
			end = mid - 1;
		}
		else
		{
			start = mid + 1;
		}
	}
	return -1;
}
int main()
{
	sort(arr, arr + 8);
	for (int i : arr) cout << i << " ";
	cout << "\n";
	int ret = binary_search(0, 7);
	cout << ret << "번 인덱스\n";
	return 0;
}