Binary Serach

Binary Search 이진탐색

• 순차 탐색 : 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 방법.
• 이진 탐색 : 탐색 범위를 절반씩 줄어가며 값을 찾는 방법. 탐색 전, 배열이 미리 정렬되어 있어야한다.

배열의 크기가 N이라고 할때,

	순차탐색	이진탐색
시간복잡도	O(N)	O(log N)

• 탐색 방법

 크기가 N인 배열 arr에서, target을 찾는다고 가정 시

1. start = 0, end = N-1 로 초기화 한다.
2. mid = (start + end) / 2 로 초기화 한다.
3. target과 arr[mid]의 값을 비교한다. 값이 같을 시, 탐색을 종료

    같지 않을시, target < data[mid] 이면 end = mid-1로 업데이트 후 2번으로 돌아감

                      target > data[mid] 이면 start = mid+1로 업데이트 후 2번으로 돌아감

• 문제에서 사용할 때의 while문?

    while(end > start)면 start = mid + 1, end = mid

    while(end >= start)면 start = mid + 1, end = mid - 1