{"type": "doc", "content": [{"type": "paragraph", "content": [{"text": "lower bound는 한국말로 '하한' 이라는 의미다. 5의 lower bound는, 5 이상의 값이 나오는 최초의 위치이다. 반면 upper bound는 한국말로 '상한' 이라는 의미이다. 5의 upper bound는, 5 초과의 값이 나오는 최초의 위치이다.", "type": "text"}]}, {"type": "paragraph", "content": [{"text": "이 때, 이분탐색에서 lower bound, upper bound 를 구할 때 주의점이 한가지 있다. 바로, 데이터들의 최대값보다 큰 값, 혹은 최소값보다 작은 값을 구할 경우에 문제가 된다.", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "heading", "attrs": {"level": 1}, "content": [{"text": "1. Lower Bound", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "heading", "attrs": {"level": 2}, "content": [{"text": "(1) 데이터의 최대값보다 큰 값의 lower bound", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "blockquote", "content": [{"type": "paragraph", "content": [{"text": "<문제 조건>", "type": "text", "marks": [{"type": "bold"}]}, {"text": " ", "type": "text"}, {"text": "[0, 1, 3, 5, 5, 5, 7, 9, 9, 10, 10, 12, 14] 배열에서 15의 lower bound를 찾아라", "type": "text", "marks": [{"type": "bold"}]}]}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "paragraph", "content": [{"text": "먼저 다음처럼 lower bound를 구하고자 하는 이진 탐색 함수를 작성했다고 하자.", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "codeBlock", "attrs": {"language": "java"}, "content": [{"text": "public static int getLowerBound(int[] arr, int h){\n int l = 0, r = arr.length-1;\n while(l < r) {\n int mid = (l + r) / 2;\n if (arr[mid] < h) {\n l = mid + 1;\n } else {\n r = mid;\n }\n }\n return l;\n}", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "image", "attrs": {"alt": "", "src": "https://velog.velcdn.com/images/goat_hoon/post/0e866bbc-869b-4005-b605-087a28d1a16d/image.png", "title": null, "width": null, "height": null}}, {"type": "paragraph", "content": [{"text": " 그럼 답은 12가 나온다. 내가 원한 값은 13이어야 할텐데, 12가 나온다는 것은 문제가 된다. 문제의 원인은, 오른쪽 끝 원소의 위치가 항상 탐색 값보다 작다는 것이 가장 큰 문제이다.", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "paragraph", "content": [{"text": "이는 두가지로 해결할 수 있다.", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "heading", "attrs": {"level": 3}, "content": [{"text": "(1) 오른쪽 끝을 arr의 배열의 크기로 두자 (마지막 index + 1)", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "paragraph", "content": [{"text": "오른쪽 끝 원소의 위치가 항상 탐색 값보다 작다는 것을 해결하기 위해, 임시의 index를 추가한 것이다. 이렇게 추가해도 문제가 없는 이유는, 해당 배열 범위의 최대값보다 작은 데이터를 탐색한다면, 어차피 ", "type": "text"}, {"text": "R", "type": "text", "marks": [{"type": "code"}]}, {"text": " 은 유효한 index내로 이동할 것이다. 만일 그렇지 않은 경우에, 하한선은 R의 위치가 되어 문제의 조건을 만족한다.", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "codeBlock", "attrs": {"language": "java"}, "content": [{"text": "public static int getLowerBound(int[] arr, int h){\n int l = 0, r = arr.length;\n while(l < r) {\n int mid = (l + r) / 2;\n if (arr[mid] < h) {\n l = mid + 1;\n } else {\n r = mid;\n }\n }\n return l;\n}", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "image", "attrs": {"alt": "", "src": "https://velog.velcdn.com/images/goat_hoon/post/46216306-acb0-4f5a-be10-8cf36a7f084a/image.png", "title": null, "width": null, "height": null}}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "heading", "attrs": {"level": 3}, "content": [{"text": "(2) 구현문을 바꿔버리자", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "paragraph", "content": [{"text": "구현된 코드의 문제점은 ", "type": "text"}, {"text": "l==r", "type": "text", "marks": [{"type": "code"}]}, {"text": " 의 위치인 12에서 반복문이 끝나기 때문이다. 이를 해결하기 위해서는, 해당 반복문을 빠져나갈 수 있게 while 반복문에 등호를 포함시키고, 이를 종료할 수 있게하는 ", "type": "text"}, {"text": "l", "type": "text", "marks": [{"type": "code"}]}, {"text": "과 ", "type": "text"}, {"text": "r", "type": "text", "marks": [{"type": "code"}]}, {"text": "의 조건을 상정하면 된다. 당연히 ", "type": "text"}, {"text": "l = mid + 1", "type": "text", "marks": [{"type": "code"}]}, {"text": " 로 유지이고, ", "type": "text"}, {"text": "r = mid - 1", "type": "text", "marks": [{"type": "code"}]}, {"text": " 로 변경해서, r의 종료도 신경쓰자.", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "codeBlock", "attrs": {"language": "java"}, "content": [{"text": "public static int getLowerBound(int[] arr, int h){\n int l = 0, r = arr.length;\n while(l <= r) {\n int mid = (l + r) / 2;\n if (arr[mid] < h) {\n l = mid + 1;\n } else {\n r = mid - 1;\n }\n }\n return l;\n}", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "image", "attrs": {"alt": "", "src": "https://velog.velcdn.com/images/goat_hoon/post/f2f32934-6eb0-4fe3-ae94-92265b6aab5f/image.png", "title": null, "width": null, "height": null}}, {"type": "image", "attrs": {"alt": "", "src": "https://velog.velcdn.com/images/goat_hoon/post/90e08c91-090c-4501-a19f-2d41f44e9396/image.png", "title": null, "width": null, "height": null}}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "heading", "attrs": {"level": 2}, "content": [{"text": "(2) 데이터의 최소값보다 작은 값의 lower bound", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "paragraph", "content": [{"text": "이 경우는 lower bound가 존재할 수가 없다.", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "heading", "attrs": {"level": 1}, "content": [{"text": "2. Upper Bound", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "paragraph", "content": [{"text": "Lower Bound와 원리는 마찬가지다. 다음 두가지 코드로 구현 가능하다.", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "codeBlock", "attrs": {"language": "java"}, "content": [{"text": "public static int upper(int x, int[] arr){\n int l = 0, r = arr.length;\n while(l < r){\n int mid = (l+r)/2;\n if(arr[mid] > x){\n r = mid;\n }\n else{\n l = mid+1;\n }\n }\n return l;\n}", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "codeBlock", "attrs": {"language": "java"}, "content": [{"text": "public static int upper(int x, int[] arr){\n int l = 0, r = arr.length-1;\n while(l <= r){\n int mid = (l+r)/2;\n if(arr[mid] > x){\n r = mid-1;\n }\n else{\n l = mid+1;\n }\n }\n return l;\n}", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "heading", "attrs": {"level": 1}, "content": [{"text": "마무리", "type": "text"}]}, {"type": "paragraph", "content": [{"text": " ", "type": "text"}]}, {"type": "paragraph", "content": [{"text": "개인적으로 ", "type": "text"}, {"text": "while(l

[Java Spring] @RequestBody 빈생성자