정의

정렬된 배열에서 first와 last 의 가운데인 mid 값이 찾고자 하는 값보다 크거나 작거나 또는 같은지 여부에 따라 지속적으로 이분할해서 탐색하는 원리

시간 복잡도 O(logN)

반복문 또는 재귀함수로 구현 가능 => 탈출 설정을 잘 이해해야 한다

탈출조건

• first 가 last 보다 커질 때 => 원하는 값이 배열에 없음을 의미
• 값을 찾으면 탈출

반복문에선 while ( first <= last ) 과 같은 경우에만 실행,
first 와 last 가 만나는 시점에서 종료할 시 해당 위치의 데이터는 검사하지 않고 끝나기 때문

구현 예시

while(first <= last)
{
    mid = (first + last) / 2;
    if(target == array[mid])
    	return mid;
    else
    {
    	if(target < array[mid])
        	last = mid - 1;
        else
        	first = mid + 1;
    }
}