{"type":"doc","content":[{"type":"extension","attrs":{"layout":"default","extensionType":"com.atlassian.confluence.macro.core","extensionKey":"toc","parameters":{"macroParams":{"style":{"value":"none"}},"macroMetadata":{"macroId":{"value":"4bdebfc0-3839-47bd-9729-a324229184dc"},"schemaVersion":{"value":"1"},"title":"Table of Contents"}},"localId":"04096353-d389-40dc-aece-496f7d52edf1"}},{"type":"heading","attrs":{"level":1},"content":[{"text":"二分查找","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 704. Binary Search 二分查找","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/binary-search/"}}]},{"type":"paragraph","content":[{"text":" 给定一个【有序】【不重复】数组和一个目标值，找到这个元素的索引；如果不存在，返回 -1","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func search(nums []int, target int) int {\n left, right := 0, len(nums)\n \n for left < right {\n mid := left + (right - left) / 2\n \n if nums[mid] == target {\n return mid\n } else if nums[mid] < target {\n left = mid + 1\n } else { // nums[mid] > target\n right = mid\n }\n }\n \n return -1 // not found\n}","type":"text"}]},{"type":"paragraph","content":[{"text":"一般算法中使用的都是 ","type":"text"},{"text":"[left, right)","type":"text","marks":[{"type":"code"}]},{"text":" 区间","type":"text"}]},{"type":"expand","attrs":{"title":"如果想要 [left, right] 区间的话"},"content":[{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func search(nums []int, target int) int {\n left, right := 0, len(nums)-1\n \n for left <= right {\n mid := left + (right - left) / 2\n \n if nums[mid] == target {\n return mid\n } else if nums[mid] < target {\n left = mid + 1\n } else { // nums[mid] > target\n right = mid - 1\n }\n }\n \n return -1 // not found\n}","type":"text"}]}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"二分查找【寻找左侧边界】","type":"text"}]},{"type":"paragraph","content":[{"text":" 给定一个【有序】【可能重复】数组和一个目标值，找到这个元素的索引（如果存在多个，返回最左侧的索引）；如果不存在，返回 -1","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func searchLeft(nums []int, target int) int {\n left, right := 0, len(nums)\n \n for left < right {\n mid := left + (right - left) / 2\n \n if nums[mid] >= target {\n right = mid\n } else {\n left = mid + 1\n }\n }\n \n // 此时 left=right\n // 算法核心思想为【持续收缩右边界至 >= target 的最小索引】\n // -> 如果 target < min(nums) 返回 0\n // -> 如果 target > max(nums) 返回 len(nums)\n \n if right >= len(nums) || nums[right] != target {\n // NOTE: 此时 right 是【大于 target 的最小索引】\n // 例如：[1, 3, 5, 7] target=4\n // 返回的是 2 <- 指向了 5\n \n return -1\n }\n \n return right\n}","type":"text"}]},{"type":"paragraph","content":[{"text":"可利用牛客进行测试：","type":"text"},{"type":"inlineCard","attrs":{"url":"https://www.nowcoder.com/questionTerminal/28d5a9b7fc0b4a078c9a6d59830fb9b9"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"c++"},"content":[{"text":"class BinarySearch {\npublic:\n int getPos(vector nums, int n, int target) {\n int left = 0, right = n;\n\n while (left < right) {\n int mid = left + (right - left) / 2;\n\n if (nums[mid] >= target) {\n right = mid;\n } else {\n left = mid + 1;\n }\n }\n\n if (right >= n || nums[right] != target) {\n return -1;\n }\n\n return right;\n }\n};","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"二分查找【寻找右侧边界】","type":"text"}]},{"type":"paragraph","content":[{"text":"给定一个【有序】【可能重复】数组和一个目标值，找到这个元素的索引（如果存在多个，返回最右侧的索引）；如果不存在，返回 -1","type":"text"}]},{"type":"paragraph","content":[{"text":"方法一","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","content":[{"text":"func searchRight(nums []int, target int) int {\n left, right := 0, len(nums)\n \n for left < right {\n mid := left + (right - left) / 2\n \n if nums[mid] <= target {\n left = mid + 1\n } else if nums[mid] > target {\n right = mid\n }\n }\n \n // 算法核心思想为【持续收缩左边界至 <= target 的最大索引 + 1】\n \n if left <= 0 {\n return -1\n }\n \n return left - 1\n}\n","type":"text"}]},{"type":"paragraph","content":[{"text":"整体思路刚好与 ","type":"text"},{"text":"searchLeft","type":"text","marks":[{"type":"code"}]},{"text":" 相反，为收缩左边届 —— ","type":"text"}]},{"type":"paragraph","content":[{"text":"方法二：利用 leftBound","type":"text","marks":[{"type":"strong"}]}]},{"type":"paragraph","content":[{"text":"上一题的 ","type":"text"},{"text":"searchLeft","type":"text","marks":[{"type":"code"}]},{"text":" 中其实隐含了一个「找到 >= target 的最小索引」的方案（称为 ","type":"text"},{"text":"leftBound","type":"text","marks":[{"type":"code"}]},{"text":"）","type":"text"}]},{"type":"paragraph","content":[{"text":"利用 ","type":"text"},{"text":"leftBound","type":"text","marks":[{"type":"code"}]},{"text":" 可知，找到「== x 的最右侧索引」问题可以转换为找到「>= x+1 的最左侧索引再 -1」即 ","type":"text"},{"text":"leftBound(target+1)-1","type":"text","marks":[{"type":"code"}]}]},{"type":"codeBlock","content":[{"text":"func searchRight(nums []int, target int) int {\n // 寻找 target 的右边界 = 寻找 >= target+1 的元素的左边届-1\n x := leftBound(nums, target + 1) - 1\n \n // 注意此时 target+1 过小时，x = -1\n if x == -1 || nums[x] != target {\n return -1\n }\n \n return x\n}\n\n// 返回 >= target 的最小索引\nfunc leftBound(nums []int, target int) int {\n left, right := 0, len(nums)\n \n for left < right {\n mid := left + (right - left) / 2\n \n if nums[mid] >= target {\n right = mid\n } else {\n left = mid + 1\n }\n }\n \n return right\n}\n\n// 上面的 leftBound 是从之前的 searchLeft 中拆出来的 —— 利用 leftBound 重写 searchLeft 的话如下\nfunc searchLeft(nums []int, target int) int {\n x := leftBound(nums, target)\n \n if x >= len(nums) || nums[x] != target {\n return -1\n }\n \n return x\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC.34 Find. First and Last Position of Element in Sorted Array 在排序数组中找元素的第一个和最后一个位置【寻找左右边界】","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/"}},{"text":" ","type":"text"}]},{"type":"paragraph","content":[{"text":"利用 ","type":"text"},{"text":"leftBound","type":"text","marks":[{"type":"code"}]},{"text":" 完成：","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func searchRange(nums []int, target int) []int {\n l := searchLeft(nums, target)\n if l == -1 {\n return []int{-1, -1}\n }\n r := searchRight(nums, target)\n \n return []int{l, r}\n}\n\nfunc searchLeft(nums []int, target int) int {\n x := leftBound(nums, target)\n \n if x >= len(nums) || nums[x] != target {\n return -1\n }\n \n return x\n}\n\nfunc searchRight(nums []int, target int) int {\n // 寻找 target 的右边界 = 寻找 >= target+1 的元素的左边届-1\n x := leftBound(nums, target + 1) - 1\n \n // 注意此时 target+1 过小时，x = -1\n if x == -1 || nums[x] != target {\n return -1\n }\n \n return x\n}\n\n// 返回 >= target 的最小索引\nfunc leftBound(nums []int, target int) int {\n left, right := 0, len(nums)\n \n for left < right {\n mid := left + (right - left) / 2\n \n if nums[mid] >= target {\n right = mid\n } else {\n left = mid + 1\n }\n }\n \n return right\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LCCN LCR 172. 统计目标成绩的出现次数","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/description/"}},{"text":" ","type":"text"}]},{"type":"paragraph","content":[{"text":"本题与上一题几乎一样（只有返回值不一样）","type":"text"}]},{"type":"paragraph","content":[{"text":"采用 ","type":"text"},{"text":"rightBound","type":"text","marks":[{"type":"code"}]},{"text":" 完成：","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func countTarget(scores []int, target int) int {\n l := searchLeft(scores, target)\n if l == -1 {\n // score not exist\n return 0\n }\n r := searchRight(scores, target)\n return r-l+1\n}\n\nfunc searchLeft(nums []int, target int) int {\n x := rightBound(nums, target-1) + 1\n if x >= len(nums) || nums[x] != target {\n return -1\n }\n return x\n}\n\nfunc searchRight(nums []int, target int) int {\n x := rightBound(nums, target)\n if x < 0 || nums[x] != target {\n return -1\n }\n return x\n}\n\n// 返回 <= target 的最大索引\nfunc rightBound(nums []int, target int) int {\n left, right := 0, len(nums)\n\n for left < right {\n mid := left + (right - left) / 2\n\n if nums[mid] <= target {\n left = mid + 1\n } else{\n right = mid\n }\n }\n\n return left - 1\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC.278 First Bad Version 第一个错误的版本","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"/** \n * Forward declaration of isBadVersion API.\n * @param version your guess about first bad version\n * @return \t \t true if current version is bad \n *\t\t\t false if current version is good\n * func isBadVersion(version int) bool;\n */\n\nfunc firstBadVersion(n int) int {\n l, r := 1, n+1\n for l < r {\n mid := l + (r - l) / 2\n \n if isBadVersion(mid) {\n // >= mid all bad\n r = mid\n } else {\n l = mid + 1\n }\n }\n \n return r\n}","type":"text"}]},{"type":"paragraph"}],"version":1}