[C++][구현] Binary Search

검색 할 때 쓰는 알고리즘으로 O(log n) 만큼의 시간 복잡도를 가지고 있습니다.

 

또한 사전 작업으로 정렬이 미리 돼어있어야지 사용할 수 있습니다.

 

#include <iostream>
using namespace std;

int search(int nums[], int length, int target) {
	int left = 0;
	int right = length -1;
	while (left <= right) {
		int pivot = (left + right) / 2;

		// 찾았을 때
		if (nums[pivot] == target) {
			return pivot;
		}

		// 검색 값 < target
		else if (nums[pivot] < target) {
			left = pivot + 1;
		}

		// 검색 값 > target
		else { // nums[pivot] > target
			right = pivot - 1;
		}
	}
	
	return -1;
}

 

 

주요 알고리즘은, left, right, pivot을 통하여, 지속적으로 갱신을 해주며 값을 찾아내는 알고리즘입니다.