이진 탐색 너무 어려운 것 같아요......
혹시 어떻게 풀 수 있나요?
솔직히 이진탐색은 아직 감도 못잡겠어요,,,,,,
크게 이진탐색을 볼 때, 세가지 정도가 문제가 되는 것 같아요
1. 탈출 조건. 언제 break 혹은 return 하는가(input이 배열인 경우 mid 조건 혹은 left>right / left>=right
2. 바운더리 초기화 조건. 보통 l = 0 / l = 1 or r = size(input) -1 / r = size(input)
3. 바운더리 선택 조건. l = mid or l = mid + 1 | r = mid or r = mid -1
각각의 대표 케이스를 외우고, 비슷한 경우가 나오면 그냥 외워서 때려 박으면 되는데
각각 케이스에 대해서, 왜 이렇게 바운더리를 초기화 해야 하고, 선택 해야 하는지에 대해 이유를 설명을 못하겠어요.....
그러니까 이론 상으로 이진 탐색이 무엇인가를 말할 수 있는데, 실제 문제에서 엣지 케이스를 선택하고 버리는 부분에 대해 전혀 모르는 느낌.....
그냥 양치기 하고 외우는게 답인가요?
아니면, 좀 감을 잡을 수 있는 이해 방법이 있을까요?
백준에 깔끔하게 정리된 글 하나 있는데 그거 읽어보는거 어떰
오 어디 있나요
https://www.acmicpc.net/blog/view/109
요 글인가요?ㅎㅎㅎ
https://www.acmicpc.net/blog/view/109
오 감사합니다
x = "OK인 점", y = "NO인 점"일 때, 중간점 m = (x+y)/2가 OK인지 NO인지 탐색해 본다라고 생각하면 됨. 탈출조건은 OK인 점 바로 다음에 NO인 점이 있을 때 까지 (x+1 == y이거나 y+1 == x이거나, x y 대소관계에 따라 케바케). "OK인 점"을 뭔지 정하는게 이분탐색의 핵심이라고 생각함.
예시: 정렬된 행렬 A에서 어떤 값 v 찾기: A[x] <= v면 OK인 점, 아니면 NO인 점이라고 두고, 우선 A[1]이랑 A[마지막] 확인 (굳이 안 해도 되지만 이러는게 맘 편함.) A[1]이 OK고 A[마지막]이 NO면 x=1, y=마지막으로 두고 이분탐색 반복. 이분탐색 끝내면 A[x] 왼쪽에 있는 것들... <= A[x] <= v < A[y] <= A[y] 오른쪽에 있는 것들...이니까 A[x]가 v인지만 검사하면 됨.