[leetCode] D-1. Binary Search (14 days study plan to crack algo)

이진 탐색 ( Binary Search )

정렬된 배열에서 특정 값을 찾을 때 사용할 수 있는 알고리즘이다.

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식.

처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

시간 복잡도는 O(logN)으로 빠르다.

관련 문제

leetCode - 14days study plan to crack algo
day1. binary search에 해당하는 문제 풀이 포스팅

• [leetCode] 35. Search Insert Position
• [leetCode] 278. First Bad Version

Reference

• https://takeuu.tistory.com/171 [워너비스페셜]