8000 algorithm-pattern/basic_algorithm/binary_search.md at master · greyireland/algorithm-pattern · GitHub
[go: up one dir, main page]
Skip to content
{"payload":{"allShortcutsEnabled":false,"fileTree":{"basic_algorithm":{"items":[{"name":"binary_search.md","path":"basic_algorithm/binary_search.md","contentType":"file"},{"name":"dp.md","path":"basic_algorithm/dp.md","contentType":"file"},{"name":"sort.md","path":"basic_algorithm/sort.md","contentType":"file"}],"totalCount":3},"":{"items":[{"name":"advanced_algorithm","path":"advanced_algorithm","contentType":"directory"},{"name":"basic_algorithm","path":"basic_algorithm","contentType":"directory"},{"name":"data_structure","path":"data_structure","contentType":"directory"},{"name":"images","path":"images","contentType":"directory"},{"name":"introduction","path":"introduction","contentType":"directory"},{"name":"practice_algorithm","path":"practice_algorithm","contentType":"directory"},{"name":"src","path":"src","contentType":"directory"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":"LICENSE","path":"LICENSE","contentType":"file"},{"name":"README.md","path":"README.md","contentType":"file"},{"name":"SUMMARY.md","path":"SUMMARY.md","contentType":"file"},{"name":"TODO.md","path":"TODO.md","contentType":"file"}],"totalCount":12}},"fileTreeProcessingTime":9.438132999999999,"foldersToFetch":[],"incompleteFileTree":false,"repo":{"id":272035489,"defaultBranch":"master","name":"algorithm-pattern","ownerLogin":"greyireland","currentUserCanPush":false,"isFork":false,"isEmpty":false,"createdAt":"2020-06-13T15:29:21.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/9276742?v=4","public":true,"private":false,"isOrgOwned":false},"codeLineWrapEnabled":false,"symbolsExpanded":false,"treeExpanded":true,"refInfo":{"name":"master","listCacheKey":"v0:1674272582.362138","canEdit":false,"refType":"branch","currentOid":"0a8d0cf6644b36f557570aca89bb929bff248f41"},"path":"basic_algorithm/binary_search.md","currentUser":null,"blob":{"rawLines":null,"stylingDirectives":null,"colorizedLines":null,"csv":null,"csvError":null,"dependabotInfo":{"showConfigurationBanner":false,"configFilePath":null,"networkDependabotPath":"/greyireland/algorithm-pattern/network/updates","dismissConfigurationNoticePath":"/settings/dismiss-notice/dependabot_configuration_notice","configurationNoticeDismissed":null},"displayName":"binary_search.md","displayUrl":"https://github.com/greyireland/algorithm-pattern/blob/master/basic_algorithm/binary_search.md?raw=true","headerInfo":{"blobSize":"13 KB","deleteTooltip":"You must be signed in to make or propose changes","editTooltip":"You must be signed in to make or propose changes","ghDesktopPath":"https://desktop.github.com","isGitLfs":false,"onBranch":true,"shortPath":"15f336a","siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fgreyireland%2Falgorithm-pattern%2Fblob%2Fmaster%2Fbasic_algorithm%2Fbinary_search.md","isCSV":false,"isRichtext":true,"toc":[{"level":1,"text":"二分搜索","anchor":"二分搜索","htmlText":"二分搜索"},{"level":2,"text":"二分搜索模板","anchor":"二分搜索模板","htmlText":"二分搜索模板"},{"level":2,"text":"常见题目","anchor":"常见题目","htmlText":"常见题目"},{"level":3,"text":"search-for-range","anchor":"search-for-range","htmlText":"search-for-range"},{"level":3,"text":"search-insert-position","anchor":"search-insert-position","htmlText":"search-insert-position"},{"level":3,"text":"search-a-2d-matrix","anchor":"search-a-2d-matrix","htmlText":"search-a-2d-matrix"},{"level":3,"text":"first-bad-version","anchor":"first-bad-version","htmlText":"first-bad-version"},{"level":3,"text":"find-minimum-in-rotated-sorted-array","anchor":"find-minimum-in-rotated-sorted-array","htmlText":"find-minimum-in-rotated-sorted-array"},{"level":3,"text":"find-minimum-in-rotated-sorted-array-ii","anchor":"find-minimum-in-rotated-sorted-array-ii","htmlText":"find-minimum-in-rotated-sorted-array-ii"},{"level":3,"text":"search-in-rotated-sorted-array","anchor":"search-in-rotated-sorted-array","htmlText":"search-in-rotated-sorted-array"},{"level":3,"text":"search-in-rotated-sorted-array-ii","anchor":"search-in-rotated-sorted-array-ii","htmlText":"search-in-rotated-sorted-array-ii"},{"level":2,"text":"总结","anchor":"总结","htmlText":"总结"},{"level":2,"text":"练习题","anchor":"练习题","htmlText":"练习题"}],"lineInfo":{"truncatedLoc":"423","truncatedSloc":"374"},"mode":"file"},"image":false,"isCodeownersFile":null,"isPlain":false,"isValidLegacyIssueTemplate":false,"issueTemplate":null,"discussionTemplate":null,"language":"Markdown","languageID":222,"large":false,"planSupportInfo":{"repoIsFork":null,"repoOwnedByCurrentUser":null,"requestFullPath":"/greyireland/algorithm-pattern/blob/master/basic_algorithm/binary_search.md","showFreeOrgGatedFeatureMessage":null,"showPlanSupportBanner":null,"upgradeDataAttributes":null,"upgradePath":null},"publishBannersInfo":{"dismissActionNoticePath":"/settings/dismiss-notice/publish_action_from_dockerfile","releasePath":"/greyireland/algorithm-pattern/releases/new?marketplace=true","showPublishActionBanner":false},"rawBlobUrl":"https://github.com/greyireland/algorithm-pattern/raw/refs/heads/master/basic_algorithm/binary_search.md","renderImageOrRaw":false,"richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e二分搜索\u003c/h1\u003e\u003ca id=\"user-content-二分搜索\" class=\"anchor\" aria-label=\"Permalink: 二分搜索\" href=\"#二分搜索\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e二分搜索模板\u003c/h2\u003e\u003ca id=\"user-content-二分搜索模板\" class=\"anchor\" aria-label=\"Permalink: 二分搜索模板\" href=\"#二分搜索模板\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e给一个\u003cstrong\u003e有序数组\u003c/strong\u003e和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回-1\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e模板四点要素\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e1、初始化：start=0、end=len-1\u003c/li\u003e\n\u003cli\u003e2、循环退出条件：start + 1 \u0026lt; end\u003c/li\u003e\n\u003cli\u003e3、比较中点和目标值：A[mid] ==、 \u0026lt;、\u0026gt; target\u003c/li\u003e\n\u003cli\u003e4、判断最后两个元素是否符合：A[start]、A[end] ? target\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e时间复杂度 O(logn)，使用场景一般是有序数组的查找\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e典型示例\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca href=\"https://leetcode-cn.com/problems/binary-search/\" rel=\"nofollow\"\u003ebinary-search\u003c/a\u003e\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e给定一个  n  个元素有序的（升序）整型数组  nums 和一个目标值  target  ，写一个函数搜索  nums  中的 target，如果目标值存在返回下标，否则返回 -1。\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"highlight highlight-source-go notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"// 二分搜索最常用模板\nfunc search(nums []int, target int) int {\n // 1、初始化start、end\n start := 0\n end := len(nums) - 1\n // 2、处理for循环\n for start+1 \u0026lt; end {\n mid := start + (end-start)/2\n // 3、比较a[mid]和target值\n if nums[mid] == target {\n end = mid\n } else if nums[mid] \u0026lt; target {\n start = mid\n } else if nums[mid] \u0026gt; target {\n end = mid\n }\n }\n // 4、最后剩下两个元素，手动判断\n if nums[start] == target {\n return start\n }\n if nums[end] == target {\n return end\n }\n return -1\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-c\"\u003e// 二分搜索最常用模板\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003efunc\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esearch\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e []\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e) \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 1、初始化start、end\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-c\"\u003e// 2、处理for循环\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e)\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\n \u003cspan class=\"pl-c\"\u003e// 3、比较a[mid]和target值\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n }\n }\n \u003cspan class=\"pl-c\"\u003e// 4、最后剩下两个元素，手动判断\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\n }\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\n }\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n}\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e大部分二分查找类的题目都可以用这个模板，然后做一点特殊逻辑即可\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e另外二分查找还有一些其他模板如下图，大部分场景模板#3 都能解决问题，而且还能找第一次/最后一次出现的位置，应用更加广泛\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/ac1a8cdef67c491ce117a4fd77d5462b00fb73ddbfd60a5bc709f66834641844/68747470733a2f2f696d672e667569626f6f6d2e636f6d2f696d672f62696e6172795f7365617263685f74656d706c6174652e706e67\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/ac1a8cdef67c491ce117a4fd77d5462b00fb73ddbfd60a5bc709f66834641844/68747470733a2f2f696d672e667569626f6f6d2e636f6d2f696d672f62696e6172795f7365617263685f74656d706c6174652e706e67\" alt=\"binary_search_template\" data-canonical-src=\"https://img.fuiboom.com/img/binary_search_template.png\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e所以用模板#3 就对了，详细的对比可以这边文章介绍：\u003ca href=\"https://leetcode-cn.com/explore/learn/card/binary-search/212/template-analysis/847/\" rel=\"nofollow\"\u003e二分搜索模板\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e如果是最简单的二分搜索，不需要找第一个、最后一个位置、或者是没有重复元素，可以使用模板#1，代码更简洁\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-go notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"// 无重复元素搜索时，更方便\nfunc search(nums []int, target int) int {\n start := 0\n end := len(nums) - 1\n for start \u0026lt;= end {\n mid := start + (end-start)/2\n if nums[mid] == target {\n return mid\n } else if nums[mid] \u0026lt; target {\n start = mid+1\n } else if nums[mid] \u0026gt; target {\n end = mid-1\n }\n }\n // 如果找不到，start 是第一个大于target的索引\n // 如果在B+树结构里面二分搜索，可以return start\n // 这样可以继续向子节点搜索，如：node:=node.Children[start]\n return -1\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-c\"\u003e// 无重复元素搜索时，更方便\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003efunc\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esearch\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e []\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e) \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e)\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n }\n }\n \u003cspan class=\"pl-c\"\u003e// 如果找不到，start 是第一个大于target的索引\u003c/span\u003e\n \u003cspan class=\"pl-c\"\u003e// 如果在B+树结构里面二分搜索，可以return start\u003c/span\u003e\n \u003cspan class=\"pl-c\"\u003e// 这样可以继续向子节点搜索，如：node:=node.Children[start]\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n}\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e常见题目\u003c/h2\u003e\u003ca id=\"user-content-常见题目\" class=\"anchor\" aria-label=\"Permalink: 常见题目\" href=\"#常见题目\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e\u003ca href=\"https://www.lintcode.com/problem/search-for-a-range/description\" rel=\"nofollow\"\u003esearch-for-range\u003c/a\u003e\u003c/h3\u003e\u003ca id=\"user-content-search-for-range\" class=\"anchor\" aria-label=\"Permalink: search-for-range\" href=\"#search-for-range\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。\n如果目标值不在数组中，则返回\u003ccode\u003e[-1, -1]\u003c/code\u003e\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cp dir=\"auto\"\u003e思路：核心点就是找第一个 target 的索引，和最后一个 target 的索引，所以用两次二分搜索分别找第一次和最后一次的位置\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-go notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func searchRange (A []int, target int) []int {\n if len(A) == 0 {\n return []int{-1, -1}\n }\n result := make([]int, 2)\n start := 0\n end := len(A) - 1\n for start+1 \u0026lt; end {\n mid := start + (end-start)/2\n if A[mid] \u0026gt; target {\n end = mid\n } else if A[mid] \u0026lt; target {\n start = mid\n } else {\n // 如果相等，应该继续向左找，就能找到第一个目标值的位置\n end = mid\n }\n }\n // 搜索左边的索引\n if A[start] == target {\n result[0] = start\n } else if A[end] == target {\n result[0] = end\n } else {\n result[0] = -1\n result[1] = -1\n return result\n }\n start = 0\n end = len(A) - 1\n for start+1 \u0026lt; end {\n mid := start + (end-start)/2\n if A[mid] \u0026gt; target {\n end = mid\n } else if A[mid] \u0026lt; target {\n start = mid\n } else {\n // 如果相等，应该继续向右找，就能找到最后一个目标值的位置\n start = mid\n }\n }\n // 搜索右边的索引\n if A[end] == target {\n result[1] = end\n } else if A[start] == target {\n result[1] = start\n } else {\n result[0] = -1\n result[1] = -1\n return result\n }\n return result\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003efunc\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esearchRange\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003eA\u003c/span\u003e []\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e) []\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eA\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e []\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e{\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e, \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e}\n }\n \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emake\u003c/span\u003e([]\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e, \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e)\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eA\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e)\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eA\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eA\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 如果相等，应该继续向左找，就能找到第一个目标值的位置\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n }\n }\n \u003cspan class=\"pl-c\"\u003e// 搜索左边的索引\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eA\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e[\u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eA\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e[\u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e[\u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e[\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e\n }\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eA\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e)\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eA\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eA\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 如果相等，应该继续向右找，就能找到最后一个目标值的位置\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n }\n }\n \u003cspan class=\"pl-c\"\u003e// 搜索右边的索引\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eA\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e[\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eA\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e[\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e[\u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e[\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e\n }\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e\n}\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e\u003ca href=\"https://leetcode-cn.com/problems/search-insert-position/\" rel=\"nofollow\"\u003esearch-insert-position\u003c/a\u003e\u003c/h3\u003e\u003ca id=\"user-content-search-insert-position\" class=\"anchor\" aria-label=\"Permalink: search-insert-position\" href=\"#search-insert-position\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"highlight highlight-source-go notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func searchInsert(nums []int, target int) int {\n // 思路：找到第一个 \u0026gt;= target 的元素位置\n start := 0\n end := len(nums) - 1\n for start+1 \u0026lt; end {\n mid := start + (end-start)/2\n if nums[mid] == target {\n // 标记开始位置\n start = mid\n } else if nums[mid] \u0026gt; target {\n end = mid\n } else {\n start = mid\n }\n }\n if nums[start] \u0026gt;= target {\n return start\n } else if nums[end] \u0026gt;= target {\n return end\n } else if nums[end] \u0026lt; target { // 目标值比所有值都大\n return end + 1\n }\n return 0\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003efunc\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esearchInsert\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e []\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e) \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 思路：找到第一个 \u0026gt;= target 的元素位置\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e)\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 标记开始位置\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n }\n }\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e { \u003cspan class=\"pl-c\"\u003e// 目标值比所有值都大\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n }\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n}\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e\u003ca href=\"https://leetcode-cn.com/problems/search-a-2d-matrix/\" rel=\"nofollow\"\u003esearch-a-2d-matrix\u003c/a\u003e\u003c/h3\u003e\u003ca id=\"user-content-search-a-2d-matrix\" class=\"anchor\" aria-label=\"Permalink: search-a-2d-matrix\" href=\"#search-a-2d-matrix\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e编写一个高效的算法来判断  m x n  矩阵中，是否存在一个目标值。该矩阵具有如下特性：\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e每行中的整数从左到右按升序排列。\u003c/li\u003e\n\u003cli\u003e每行的第一个整数大于前一行的最后一个整数。\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"highlight highlight-source-go notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func searchMatrix(matrix [][]int, target int) bool {\n // 思路：将2纬数组转为1维数组 进行二分搜索\n if len(matrix) == 0 || len(matrix[0]) == 0 {\n return false\n }\n row := len(matrix)\n col := len(matrix[0])\n start := 0\n end := row*col - 1\n for start+1 \u0026lt; end {\n mid := start + (end-start)/2\n // 获取2纬数组对应值\n val := matrix[mid/col][mid%col]\n if val \u0026gt; target {\n end = mid\n } else if val \u0026lt; target {\n start = mid\n } else {\n return true\n }\n }\n if matrix[start/col][start%col] == target || matrix[end/col][end%col] == target{\n return true\n }\n return false\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003efunc\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esearchMatrix\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003ematrix\u003c/span\u003e [][]\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e) \u003cspan class=\"pl-smi\"\u003ebool\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 思路：将2纬数组转为1维数组 进行二分搜索\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003ematrix\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e||\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003ematrix\u003c/span\u003e[\u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e]) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003efalse\u003c/span\u003e\n }\n \u003cspan class=\"pl-s1\"\u003erow\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003ematrix\u003c/span\u003e)\n \u003cspan class=\"pl-s1\"\u003ecol\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003ematrix\u003c/span\u003e[\u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e])\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003erow\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003ecol\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e)\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\n \u003cspan class=\"pl-c\"\u003e// 获取2纬数组对应值\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ematrix\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003ecol\u003c/span\u003e][\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e%\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003ecol\u003c/span\u003e]\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003etrue\u003c/span\u003e\n }\n }\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ematrix\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003ecol\u003c/span\u003e][\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e%\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003ecol\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e||\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ematrix\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003ecol\u003c/span\u003e][\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e%\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003ecol\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e{\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003etrue\u003c/span\u003e\n }\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003efalse\u003c/span\u003e\n}\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e\u003ca href=\"https://leetcode-cn.com/problems/first-bad-version/\" rel=\"nofollow\"\u003efirst-bad-version\u003c/a\u003e\u003c/h3\u003e\u003ca id=\"user-content-first-bad-version\" class=\"anchor\" aria-label=\"Permalink: first-bad-version\" href=\"#first-bad-version\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。\n你可以通过调用  bool isBadVersion(version)  接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"highlight highlight-source-go notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func firstBadVersion(n int) int {\n // 思路：二分搜索\n start := 0\n end := n\n for start+1 \u0026lt; end {\n mid := start + (end - start)/2\n if isBadVersion(mid) {\n end = mid\n } else if isBadVersion(mid) == false {\n start = mid\n }\n }\n if isBadVersion(start) {\n return start\n }\n return end\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003efunc\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003efirstBadVersion\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003en\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e) \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 思路：二分搜索\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003en\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e)\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eisBadVersion\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e) {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eisBadVersion\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003efalse\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n }\n }\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eisBadVersion\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e) {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\n }\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\n}\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e\u003ca href=\"https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/\" rel=\"nofollow\"\u003efind-minimum-in-rotated-sorted-array\u003c/a\u003e\u003c/h3\u003e\u003ca id=\"user-content-find-minimum-in-rotated-sorted-array\" class=\"anchor\" aria-label=\"Permalink: find-minimum-in-rotated-sorted-array\" href=\"#find-minimum-in-rotated-sorted-array\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e假设按照升序排序的数组在预先未知的某个点上进行了旋转( 例如，数组  [0,1,2,4,5,6,7] 可能变为  [4,5,6,7,0,1,2] )。\n请找出其中最小的元素。\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"highlight highlight-source-go notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func findMin(nums []int) int {\n // 思路：/ / 最后一个值作为target，然后往左移动，最后比较start、end的值\n if len(nums) == 0 {\n return -1\n }\n start := 0\n end := len(nums) - 1\n\n for start+1 \u0026lt; end {\n mid := start + (end-start)/2\n // 最后一个元素值为target\n if nums[mid] \u0026lt;= nums[end] {\n end = mid\n } else {\n start = mid\n }\n }\n if nums[start] \u0026gt; nums[end] {\n return nums[end]\n }\n return nums[start]\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003efunc\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003efindMin\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e []\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e) \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 思路：/ / 最后一个值作为target，然后往左移动，最后比较start、end的值\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n }\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e)\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\n \u003cspan class=\"pl-c\"\u003e// 最后一个元素值为target\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n }\n }\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e]\n }\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e]\n}\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e\u003ca href=\"https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/\" rel=\"nofollow\"\u003efind-minimum-in-rotated-sorted-array-ii\u003c/a\u003e\u003c/h3\u003e\u003ca id=\"user-content-find-minimum-in-rotated-sorted-array-ii\" class=\"anchor\" aria-label=\"Permalink: find-minimum-in-rotated-sorted-array-ii\" href=\"#find-minimum-in-rotated-sorted-array-ii\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e假设按照升序排序的数组在预先未知的某个点上进行了旋转\n( 例如，数组  [0,1,2,4,5,6,7] 可能变为  [4,5,6,7,0,1,2] )。\n请找出其中最小的元素。(包含重复元素)\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"highlight highlight-source-go notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func findMin(nums []int) int {\n // 思路：跳过重复元素，mid值和end值比较，分为两种情况进行处理\n if len(nums) == 0 {\n return -1\n }\n start := 0\n end := len(nums) - 1\n for start+1 \u0026lt; end {\n // 去除重复元素\n for start \u0026lt; end \u0026amp;\u0026amp; nums[end] == nums[end-1] {\n end--\n }\n for start \u0026lt; end \u0026amp;\u0026amp; nums[start] == nums[start+1] {\n start++\n }\n mid := start + (end-start)/2\n // 中间元素和最后一个元素比较（判断中间点落在左边上升区，还是右边上升区）\n if nums[mid] \u0026lt;= nums[end] {\n end = mid\n } else {\n start = mid\n }\n }\n if nums[start] \u0026gt; nums[end] {\n return nums[end]\n }\n return nums[start]\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003efunc\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003efindMin\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e []\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e) \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 思路：跳过重复元素，mid值和end值比较，分为两种情况进行处理\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n }\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan clas BB70 s=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 去除重复元素\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u0026amp;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e] {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e--\u003c/span\u003e\n }\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u0026amp;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e] {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e++\u003c/span\u003e\n }\n \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e)\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\n \u003cspan class=\"pl-c\"\u003e// 中间元素和最后一个元素比较（判断中间点落在左边上升区，还是右边上升区）\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n }\n }\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e]\n }\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e]\n}\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e\u003ca href=\"https://leetcode-cn.com/problems/search-in-rotated-sorted-array/\" rel=\"nofollow\"\u003esearch-in-rotated-sorted-array\u003c/a\u003e\u003c/h3\u003e\u003ca id=\"user-content-search-in-rotated-sorted-array\" class=\"anchor\" aria-label=\"Permalink: search-in-rotated-sorted-array\" href=\"#search-in-rotated-sorted-array\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e假设按照升序排序的数组在预先未知的某个点上进行了旋转。\n( 例如，数组  [0,1,2,4,5,6,7]  可能变为  [4,5,6,7,0,1,2] )。\n搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回  -1 。\n你可以假设数组中不存在重复的元素。\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"highlight highlight-source-go notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func search(nums []int, target int) int {\n // 思路：/ / 两条上升直线，四种情况判断\n if len(nums) == 0 {\n return -1\n }\n start := 0\n end := len(nums) - 1\n for start+1 \u0026lt; end {\n mid := start + (end-start)/2\n // 相等直接返回\n if nums[mid] == target {\n return mid\n }\n // 判断在那个区间，可能分为四种情况\n if nums[start] \u0026lt; nums[mid] {\n if nums[start] \u0026lt;= target \u0026amp;\u0026amp; target \u0026lt;= nums[mid] {\n end = mid\n } else {\n start = mid\n }\n } else if nums[end] \u0026gt; nums[mid] {\n if nums[end] \u0026gt;= target \u0026amp;\u0026amp; nums[mid] \u0026lt;= target {\n start = mid\n } else {\n end = mid\n }\n }\n }\n if nums[start] == target {\n return start\n } else if nums[end] == target {\n return end\n }\n return -1\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003efunc\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esearch\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e []\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e) \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 思路：/ / 两条上升直线，四种情况判断\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n }\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e)\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\n \u003cspan class=\"pl-c\"\u003e// 相等直接返回\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n }\n \u003cspan class=\"pl-c\"\u003e// 判断在那个区间，可能分为四种情况\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] {\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u0026amp;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n }\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] {\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u0026amp;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n }\n }\n }\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\n }\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n}\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e注意点\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e面试时，可以直接画图进行辅助说明，空讲很容易让大家都比较蒙圈\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e\u003ca href=\"https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/\" rel=\"nofollow\"\u003esearch-in-rotated-sorted-array-ii\u003c/a\u003e\u003c/h3\u003e\u003ca id=\"user-content-search-in-rotated-sorted-array-ii\" class=\"anchor\" aria-label=\"Permalink: search-in-rotated-sorted-array-ii\" href=\"#search-in-rotated-sorted-array-ii\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e假设按照升序排序的数组在预先未知的某个点上进行了旋转。\n( 例如，数组  [0,0,1,2,2,5,6]  可能变为  [2,5,6,0,0,1,2] )。\n编写一个函数来判断给定的目标值是否存在于数组中。若存在返回  true，否则返回  false。(包含重复元素)\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"highlight highlight-source-go notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func search(nums []int, target int) bool {\n // 思路：/ / 两条上升直线，四种情况判断，并且处理重复数字\n if len(nums) == 0 {\n return false\n }\n start := 0\n end := len(nums) - 1\n for start+1 \u0026lt; end {\n // 处理重复数字\n for start \u0026lt; end \u0026amp;\u0026amp; nums[start] == nums[start+1] {\n start++\n }\n for start \u0026lt; end \u0026amp;\u0026amp; nums[end] == nums[end-1] {\n end--\n }\n mid := start + (end-start)/2\n // 相等直接返回\n if nums[mid] == target {\n return true\n }\n // 判断在那个区间，可能分为四种情况\n if nums[start] \u0026lt; nums[mid] {\n if nums[start] \u0026lt;= target \u0026amp;\u0026amp; target \u0026lt;= nums[mid] {\n end = mid\n } else {\n start = mid\n }\n } else if nums[end] \u0026gt; nums[mid] {\n if nums[end] \u0026gt;= target \u0026amp;\u0026amp; nums[mid] \u0026lt;= target {\n start = mid\n } else {\n end = mid\n }\n }\n }\n if nums[start] == target || nums[end] == target {\n return true\n }\n return false\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003efunc\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esearch\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e []\u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e) \u003cspan class=\"pl-smi\"\u003ebool\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 思路：/ / 两条上升直线，四种情况判断，并且处理重复数字\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003efalse\u003c/span\u003e\n }\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elen\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e {\n \u003cspan class=\"pl-c\"\u003e// 处理重复数字\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u0026amp;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e] {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e++\u003c/span\u003e\n }\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u0026amp;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e] {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e--\u003c/span\u003e\n }\n \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e:=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e)\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\n \u003cspan class=\"pl-c\"\u003e// 相等直接返回\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003etrue\u003c/span\u003e\n }\n \u003cspan class=\"pl-c\"\u003e// 判断在那个区间，可能分为四种情况\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] {\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u0026amp;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n }\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] {\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026gt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u0026amp;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e\u0026lt;=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003emid\u003c/span\u003e\n }\n }\n }\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003estart\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e||\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enums\u003c/span\u003e[\u003cspan class=\"pl-s1\"\u003eend\u003c/span\u003e] \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etarget\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003etrue\u003c/span\u003e\n }\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003efalse\u003c/span\u003e\n}\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e总结\u003c/h2\u003e\u003ca id=\"user-content-总结\" class=\"anchor\" aria-label=\"Permalink: 总结\" href=\"#总结\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e二分搜索核心四点要素（必背\u0026amp;理解）\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e1、初始化：start=0、end=len-1\u003c/li\u003e\n\u003cli\u003e2、循环退出条件：start + 1 \u0026lt; end\u003c/li\u003e\n\u003cli\u003e3、比较中点和目标值：A[mid] ==、 \u0026lt;、\u0026gt; target\u003c/li\u003e\n\u003cli\u003e4、判断最后两个元素是否符合：A[start]、A[end] ? target\u003c/li\u003e\n\u003c/ul\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e练习题\u003c/h2\u003e\u003ca id=\"user-content-练习题\" class=\"anchor\" aria-label=\"Permalink: 练习题\" href=\"#练习题\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul class=\"contains-task-list\"\u003e\n\u003cli class=\"task-list-item\"\u003e\u003cinput type=\"checkbox\" id=\"\" disabled=\"\" class=\"task-list-item-checkbox\"\u003e \u003ca href=\"https://www.lintcode.com/problem/search-for-a-range/description\" rel=\"nofollow\"\u003esearch-for-range\u003c/a\u003e\u003c/li\u003e\n\u003cli class=\"task-list-item\"\u003e\u003cinput type=\"checkbox\" id=\"\" disabled=\"\" class=\"task-list-item-checkbox\"\u003e \u003ca href=\"https://leetcode-cn.com/problems/search-insert-position/\" rel=\"nofollow\"\u003esearch-insert-position\u003c/a\u003e\u003c/li\u003e\n\u003cli class=\"task-list-item\"\u003e\u003cinput type=\"checkbox\" id=\"\" disabled=\"\" class=\"task-list-item-checkbox\"\u003e \u003ca href=\"https://leetcode-cn.com/problems/search-a-2d-matrix/\" rel=\"nofollow\"\u003esearch-a-2d-matrix\u003c/a\u003e\u003c/li\u003e\n\u003cli class=\"task-list-item\"\u003e\u003cinput type=\"checkbox\" id=\"\" disabled=\"\" class=\"task-list-item-checkbox\"\u003e \u003ca href=\"https://leetcode-cn.com/problems/first-bad-version/\" rel=\"nofollow\"\u003efirst-bad-version\u003c/a\u003e\u003c/li\u003e\n\u003cli class=\"task-list-item\"\u003e\u003cinput type=\"checkbox\" id=\"\" disabled=\"\" class=\"task-list-item-checkbox\"\u003e \u003ca href=\"https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/\" rel=\"nofollow\"\u003efind-minimum-in-rotated-sorted-array\u003c/a\u003e\u003c/li\u003e\n\u003cli class=\"task-list-item\"\u003e\u003cinput type=\"checkbox\" id=\"\" disabled=\"\" class=\"task-list-item-checkbox\"\u003e \u003ca href=\"https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/\" rel=\"nofollow\"\u003efind-minimum-in-rotated-sorted-array-ii\u003c/a\u003e\u003c/li\u003e\n\u003cli class=\"task-list-item\"\u003e\u003cinput type=\"checkbox\" id=\"\" disabled=\"\" class=\"task-list-item-checkbox\"\u003e \u003ca href=\"https://leetcode-cn.com/problems/search-in-rotated-sorted-array/\" rel=\"nofollow\"\u003esearch-in-rotated-sorted-array\u003c/a\u003e\u003c/li\u003e\n\u003cli class=\"task-list-item\"\u003e\u003cinput type=\"checkbox\" id=\"\" disabled=\"\" class=\"task-list-item-checkbox\"\u003e \u003ca href=\"https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/\" rel=\"nofollow\"\u003esearch-in-rotated-sorted-array-ii\u003c/a\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/article\u003e","renderedFileInfo":null,"shortPath":null,"symbolsEnabled":true,"tabSize":8,"topBannersInfo":{"overridingGlobalFundingFile":false,"globalPreferredFundingPath":null,"showInvalidCitationWarning":false,"citationHelpUrl":"https://docs.github.com/github/creating-cloning-and-archiving-repositories/creating-a-repository-on-github/about-citation-files","actionsOnboardingTip":null},"truncated":false,"viewable":true,"workflowRedirectUrl":null,"symbols":{"timed_out":false,"not_analyzed":false,"symbols":[{"name":"二分搜索","kind":"section_1","ident_start":2,"ident_end":14,"extent_start":0,"extent_end":13356,"fully_qualified_name":"二分搜索","ident_utf16":{"start":{"line_number":0,"utf16_col":2},"end":{"line_number":0,"utf16_col":6}},"extent_utf16":{"start":{"line_number":0,"utf16_col":0},"end":{"line_number":423,"utf16_col":0}}},{"name":"二分搜索模板","kind":"section_2","ident_start":19,"ident_end":37,"extent_start":16,"extent_end":2713,"fully_qualified_name":"二分搜索模板","ident_utf16":{"start":{"line_number":2,"utf16_col":3},"end":{"line_number":2,"utf16_col":9}},"extent_utf16":{"start":{"line_number":2,"utf16_col":0},"end":{"line_number":82,"utf16_col":0}}},{"name":"常见题目","kind":"section_2","ident_start":2716,"ident_end":2728,"extent_start":2713,"extent_end":12272,"fully_qualified_name":"常见题目","ident_utf16":{"start":{"line_number":82,"utf16_col":3},"end":{"line_number":82,"utf16_col":7}},"extent_utf16":{"start":{"line_number":82,"utf16_col":0},"end":{"line_number":404,"utf16_col":0}}},{"name":"[search-for-range](https://www.lintcode.com/problem/search-for-a-range/description)","kind":"section_3","ident_start":2734,"ident_end":2817,"extent_start":2730,"extent_end":4480,"fully_qualified_name":"[search-for-range](https://www.lintcode.com/problem/search-for-a-range/description)","ident_utf16":{"start":{"line_number":84,"utf16_col":4},"end":{"line_number":84,"utf16_col":87}},"extent_utf16":{"start":{"line_number":84,"utf16_col":0},"end":{"line_number":147,"utf16_col":0}}},{"name":"[search-insert-position](https://leetcode-cn.com/problems/search-insert-position/)","kind":"section_3","ident_start":4484,"ident_end":4566,"extent_start":4480,"extent_end":5396,"fully_qualified_name":"[search-insert-position](https://leetcode-cn.com/problems/search-insert-position/)","ident_utf16":{"start":{"line_number":147,"utf16_col":4},"end":{"line_number":147,"utf16_col":86}},"extent_utf16":{"start":{"line_number":147,"utf16_col":0},"end":{"line_number":178,"utf16_col":0}}},{"name":"[search-a-2d-matrix](https://leetcode-cn.com/problems/search-a-2d-matrix/)","kind":"section_3","ident_start":5400,"ident_end":5474,"extent_start":5396,"extent_end":6444,"fully_qualified_name":"[search-a-2d-matrix](https://leetcode-cn.com/problems/search-a-2d-matrix/)","ident_utf16":{"start":{"line_number":178,"utf16_col":4},"end":{"line_number":178,"utf16_col":78}},"extent_utf16":{"start":{"line_number":178,"utf16_col":0},"end":{"line_number":214,"utf16_col":0}}},{"name":"[first-bad-version](https://leetcode-cn.com/problems/first-bad-version/)","kind":"section_3","ident_start":6448,"ident_end":6520,"extent_start":6444,"extent_end":7241,"fully_qualified_name":"[first-bad-version](https://leetcode-cn.com/problems/first-bad-version/)","ident_utf16":{"start":{"line_number":214,"utf16_col":4},"end":{"line_number":214,"utf16_col":76}},"extent_utf16":{"start":{"line_number":214,"utf16_col":0},"end":{"line_number":239,"utf16_col":0}}},{"name":"[find-minimum-in-rotated-sorted-array](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/)","kind":"section_3","ident_start":7245,"ident_end":7355,"extent_start":7241,"extent_end":8086,"fully_qualified_name":"[find-minimum-in-rotated-sorted-array](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/)","ident_utf16":{"start":{"line_number":239,"utf16_col":4},"end":{"line_number":239,"utf16_col":114}},"extent_utf16":{"start":{"line_number":239,"utf16_col":0},"end":{"line_number":269,"utf16_col":0}}},{"name":"[find-minimum-in-rotated-sorted-array-ii](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/)","kind":"section_3","ident_start":8090,"ident_end":8206,"extent_start":8086,"extent_end":9225,"fully_qualified_name":"[find-minimum-in-rotated-sorted-array-ii](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/)","ident_utf16":{"start":{"line_number":269,"utf16_col":4},"end":{"line_number":269,"utf16_col":120}},"extent_utf16":{"start":{"line_number":269,"utf16_col":0},"end":{"line_number":306,"utf16_col":0}}},{"name":"[search-in-rotated-sorted-array](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/)","kind":"section_3","ident_start":9229,"ident_end":9327,"extent_start":9225,"extent_end":10713,"fully_qualified_name":"[search-in-rotated-sorted-array](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/)","ident_utf16":{"start":{"line_number":306,"utf16_col":4},"end":{"line_number":306,"utf16_col":102}},"extent_utf16":{"start":{"line_number":306,"utf16_col":0},"end":{"line_number":355,"utf16_col":0}}},{"name":"[search-in-rotated-sorted-array-ii](https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/)","kind":"section_3","ident_start":10717,"ident_end":10821,"extent_start":10713,"extent_end":12272,"fully_qualified_name":"[search-in-rotated-sorted-array-ii](https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/)","ident_utf16":{"start":{"line_number":355,"utf16_col":4},"end":{"line_number":355,"utf16_col":108}},"extent_utf16":{"start":{"line_number":355,"utf16_col":0},"end":{"line_number":404,"utf16_col":0}}},{"name":"总结","kind":"section_2","ident_start":12275,"ident_end":12281,"extent_start":12272,"extent_end":12547,"fully_qualified_name":"总结","ident_utf16":{"start":{"line_number":404,"utf16_col":3},"end":{"line_number":404,"utf16_col":5}},"extent_utf16":{"start":{"line_number":404,"utf16_col":0},"end":{"line_number":413,"utf16_col":0}}},{"name":"练习题","kind":"section_2","ident_start":12550,"ident_end":12559,"extent_start":12547,"extent_end":13356,"fully_qualified_name":"练习题","ident_utf16":{"start":{"line_number":413,"utf16_col":3},"end":{"line_number":413,"utf16_col":6}},"extent_utf16":{"start":{"line_number":413,"utf16_col":0},"end":{"line_number":423,"utf16_col":0}}}]}},"copilotInfo":null,"copilotAccessAllowed":false,"modelsAccessAllowed":false,"modelsRepoIntegrationEnabled":false,"csrf_tokens":{"/greyireland/algorithm-pattern/branches":{"post":"P9c5w1soRBQ3qBRkyE0GllULoYcGFHjw84rEhLUEM3jI8tYrvUDd8iot8Wt642JZwXhGhU_mE47JnKz_Gc5V6A"},"/repos/preferences":{"post":"IeIekgxSd2W2hKnyJ06gKPn9i3ypocdz5ZGGIqJOioC-gVAYR1toUkVYisemfPoF46ZnHp1KNn-01xoVE_49FQ"}}},"title":"algorithm-pattern/basic_algorithm/binary_search.md at master · greyireland/algorithm-pattern","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-7d7eb7c71814.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-1ae9fa256942.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true,"github_models_repo_integration":false}}}
0