이분 탐색(Binary Search)

정렬된 리스트(배열)에서 원하는 값의 존재 여부를 찾는 알고리즘

반드시 리스트(배열)를 정렬해서 사용해야 하는 단점을 가지고있음

탐색할 때마다 검사 범위가 절반으로 줄여든다.

 

재귀,반복문,STL이용하여 실행하며

재귀 : 코드 구조가 간결하고 이해하기 쉽지만 큰 배열에 대해 탐색할 경우 메모리초과 발생할 수 있음

반복문 : 재귀적 방법에 비해 코드가 약간 더 길어 질 수 있으며, 복잡해지고 이해하기 어려울 수 있음.

STL : 다양한 상황에서 안정적으로 작동하며, 범위 기반의 다양한 알고리즘 사용으로 코드 재사용성과 유연성이 높음

 

시간 복잡도는 O(log N)이다.

 

진행 과정

1. 검사 범위에서 중간 값(mid)를 선택해서 찾고자 하는 값이 같은지 확인한다.

2. 만약 찾고자 하는 값이라면 해당 값을 반환

3. 찾고자 하는 값보다 작다면 mid < target으로 검사범위를 큰쪽으로 잡는다 low = mid +1

4. 찾고자 하는 값보다 크다면 mid > target으로 검사범위를 작은 쪽으로 잡는다 high = mid -1

5. 1~4번을 반복하다가 원하는 값이 나오면 해당 값을 반환

6. 더 이상 검사할 곳이 없으면 low > high 

 

코드 구현