binary_search

특정 값을 찾을때
찾는 값이 1개 이거나 답이 1개일때 사용
완전탐색하면 O(N)이니까 O(logN) 으로 시간복잡도 줄여서 찾자는거임

재귀로 풀면 메모리제한 걸릴 수 있으니 안전하게 반복문으로 하는게 낫다
그리고 재귀 시 함수호출스택 고려하면 반복문으로 해야 더 빠름
+ 반복문이 훨씬 직관적이다
 
 

주의해야할 점은

 

1. 무조건 binary_search 전 값들은 모두 정렬된 상태여야한다는 것
2. 그리고 답이 될 수 있는 상황에는 무조건 임시로 저장해놔야한다는 것
3. mid는 확인을 한 값이므로 다음 턴은 end = mid - 1 아니면 start = mid + 1
    즉, mid를 고려하지 않는 범위로 줄여도 된다

 
답을 그냥 mid 값이라고 생각하면 안된다.
답은 "답이 가능할 때의 mid값" 이다.
 
왜냐하면 이와 같은 상황이 있을 수 있기 때문이다.
 
답 가능 -> 답 불가능 -> while(start<end) 만족 안해서 끝남
 
이러면 만약 그냥 mid를 답이라고 생각하면 답이 불가능할때의 mid값이 답이 된다
따라서 답이 가능할때 임시로 mid를 저장해놓고(ans에 저장한다고 치면)
 
while문에서 나왔을때 즉 끝까지 갔을때
return ans 를 해줘야함
 

---

[이진 탐색이 종료되는 상황의 이해]
 

 
start가 end보다 클때 이진탐색은 마지막 한 개의 원소까지 좁혀질때까지 탐색을 한 것이다
따라서 while문이 다음과 같이 되는 것임

while (start<=end) {

}

 

---

[1. 반복문]

 

vector<int> v;

int binary_search(int x)
{
    int left = 0;
    int right = v.size() - 1;
    int mid;

    while (left <= right)
    {
        mid = (left + right) / 2;

        if (x == v[mid])
        {
            return mid;
        }

        if (x < v[mid])
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }

    return left;
}

 
 

---

[2. 재귀]

 

bool BinarySearch(int* arr, int start,int end, int key) {
	if (start > end) return false;

	int mid = (start + end) / 2;

	if (arr[mid] == key) return true;
	else if (arr[mid] > key) return BinarySearch(arr, start, mid - 1, key);
	else return BinarySearch(arr, mid + 1, end, key);
}