binary search
이분 탐색 알고리즘 헷갈리는 내용 정리(while 조건, lo/hi 갱신 처리, 반환 값, lo/hi 범위)
이분 탐색을 이용한 백준 문제들을 풀다가 헷갈리는 부분들이 생겨 그에 관해 정리해본다. 일단 이분 탐색 알고리즘의 대표적인 코드를 한번 보자. int BinarySearch(int lo, int hi, int target) { while(lo + 1 < hi) { int mid = (lo + hi) / 2; if(arr[mid] target) hi = mid; } return lo; } 여기서 헷갈리는 부분들이 4가지가 있었다. while문 안의 조건 다른 사람들의 이분 탐색 코드를 살펴보면, 대표적으로 많이 쓰이는 3가지가 있다. (lo + 1 < hi), (lo < hi), (lo = target 라면, hi = mid로 갱신을 해줘야한다. while문을 탈출하는 lo + 1 == hi의 경우에, h..
이분탐색(Binary search)
- 이분탐색이란? 이분탐색이란 정렬이 되어있는 배열에서 원하는 데이터를 찾기 위해 순서대로 찾아보는 방법 대신에 탐색 범위를 절반으로 줄여나가며 찾는 탐색 방법이다. boj 문제 중에 이분탐색을 요구하는 문제가 있어서 문제를 보면서 이분탐색의 개념을 정리했다. - boj 1920 수 찾기 https://www.acmicpc.net/problem/1920 예시로 A 배열에 '3 5 6 9 10 12 14 26 35 41' 이 주어졌다고 하고, 14가 있는지 알아본다고 하자. 입력 받은 후에 sort 함수를 이용해서 정렬하면 앞과 같이 정렬된 상태일 것이다. 원래 문제는 A 안에 14가 있는지만 확인하면 되지만, 14가 A 안에서 위치하는 인덱스를 반환하는 함수를 구현해보려고 한다. st와 e..