728x90 탐색1 [탐색 알고리즘] 이진 탐색 (Binary Search) 탐색 알고리즘의 기초 중 하나인 이진 탐색. 위에 첨부한 gif가 이진 탐색의 모든 것을 설명해 준다. 이진 탐색은 오름차순으로 정렬된 정수의 리스트를 절반으로 나눈 후, 둘 중 필요한 부분만 취하는 과정을 반복해서 원하는 원소를 얻는 탐색 방법이다. 위 사진을 예로 들면, 5를 찾을 때, 우선 리스트를 중간값인 mid를 기준으로 해서 절반으로 나눈다. 여기서 mid는 4이다. 이 4가 5보다 작은지 큰지를 판단한다. 4 < 5기 때문에 오른쪽 절반 리스트만 취하고, 왼쪽 절반 리스트는 버린다. mid가 5보다 작으므로 strat를 mid+1 값으로 변경한다. 만약 5보다 크면 end를 mid-1값으로 변경했을 것이다. 이 과정을 반복하다 보면, 결국엔 mid = target인 때가 온다. 이렇게 되면 .. 2023. 6. 3. 이전 1 다음
