Data Structure & Algorithms/Binary Search1 [Binary Search] Binar Search 개념 오늘은 또다른 개념을 도전 -> 머리가 맑을때 도전하기. Binary search(BS) 는 검색 알고리즘으로 최악의 상황에서 O(log n) 의 시간 복잡도를 가진다. 여기서 n 은 검색 범위의 사이즈를 지칭한다. 검색을 위해서는 보통 sort가 되어있어야한다고 한다. Binary search의 활용은 tree ( binary search tree) 에서도 할 수 있고 array에서도 할수있는데 지금은 array에 관해서 다뤄본다. 가정으로 이미 순서대로 정리된 array가 있으면 O(log n)의 시간복잡도와 O(1)의 공간을 가진다. 이때 BS 는 어레이안에서 X 요소의 인덱스를 찾을 수 있고 첫번쨰와 마지막 인덱스를 찾을 수 있다. 릿코드 페이지에서는 구현과정을 말로 하는데 그림으로 한방으로 보는.. 2023. 2. 23. 이전 1 다음
