Re: [閒聊] 每日LeetCode

作者: fxfxxxfxx (愛麗絲)   2022-11-17 04:14:18
※ 引述《Rushia (みけねこ的鼻屎)》之銘言:
: 374. Guess Number Higher or Lower
: 龍大想要和邊板仔玩猜數字遊戲,只有龍大知道答案的數字是什麼,當我們猜的時候龍
: 大會根據你猜的數字給你一個數字:
: 龍大提供一個函數guess(int num)返回一個整數
: -1:你猜的數字太小了
: 1:你猜的數字太大了
: 0:你覺得是這個數字那就是吧- -
: 我們返回龍大才知道的數字。
今天的題目雖然是 easy
而且小時候有玩過猜數字的話應該是秒解
不過這是 binary search 蠻有趣的一個例子
因為這是一個並非在已排序陣列中找值的例子
(當然你可以說我們是在
[1, 1, ..., 1, 0, -1, -1, ..., -1]
中找 0 的位置,只是這個陣列可以非常大: 2^32 - 1
而且只能用 guess() 來獲得陣列的值)
但我要覺得這反而才比較接近 binary search 的本來樣貌
以前看過一些蠻有趣的文章,可以看一看 general 版本的 binary search
https://scm.iis.sinica.edu.tw/ncs/2010/03/binary-search-revisited/
https://scm.iis.sinica.edu.tw/ncs/2010/03/binary-search-revisited-02/
作者: surimodo (好吃棉花糖)   2022-11-17 04:17:00
中研院網址? 網管太混了吧 憑證過期不處理

Links booklink

Contact Us: admin [ a t ] ucptt.com