初看这道题的时候, 完全没想到什么二分搜索算法, 秉承我一贯的怎么简单怎么来的原则. 几乎不假思索, 写下如下代码:
for (int i = 0; i != n; ++i)
if (A[i] >= target) return i;
return n;想了想, 没啥问题, 提交, AC 了. 擦, 不对啊, 这都通过率排名第11了, 怎么如此简单呢? 于是, 看了一眼讨论, 答案都好长呀, 突然感觉那架势有点眼熟, 额, 算法第一课: 二分搜索算法. ----- 曾经我最熟练的算法了...
OK, 不再看任何东西, 擦掉重写. 二分搜索的关键在于找中点(mid), 然后两头保持一个 low 和一个 high两个标记.
if (A[mid] == target) return mid;
else if (A[mid] < target) low = mid + 1;
else high = mid - 1; // A[mid] > target.上述三个判断, 就是二分搜索的核心了.复习一下基础算法. 很有必要.
看到网友 Star 了陈皓的 LeetCode, 作为长期看他的博客, 实在按捺不住好奇心, 去看了看这道题他的代码. 果然他也用的二分搜索.(只是用的好啰嗦...), 另外居然发现他得代码有个 Bug, 汗~ 我提交了一个 issues 给他. 有点低级... 最后发现我把符号看错了... 我写的时候用的加号, 他不知为啥费劲先减后加...囧, 赶紧关闭了问题. 囧死了...
另外, 他貌似也弄了个表格在主页诶. 但是不知道是啥顺序. 看了下 Markdown, 哇撒 ,这才叫有耐心好么, 密密麻麻, 他是怎么整理的...