[討論] 給排序過的Array 用最少運算資源找值 Kuba4ma PTT批踢踢實業坊

[討論] 給排序過的Array 用最少運算資源找值

作者: Kuba4ma (哦吼) 2022-05-28 12:05:53

各位大神好
本魯最近在準備某間IC廠的面試
在網路上找到這題考古題
題目如下
```
給一個sorted array(ex: a[5]={1,1,1,0,0})，請找出第一個0的位置，請使用能降低CPU
跟memory負擔的用量
```
我能想到的就只有用for loop掃過一遍而已
請問還有更好的方法嗎
謝謝

作者: lingege321 (happyChicken) 2022-05-28 12:28:00

binary search

作者: lycantrope (阿寬) 2022-05-28 12:29:00

都sorted 就用binary search阿

作者: gozule (好冷啊~~) 2022-05-28 12:29:00

知道array長度，可以把內容轉為整數直接查表

作者: TheOneisNEO (Thomas Anderson) 2022-05-28 22:00:00

樓上說的方法應該還是要O(n) 全部都讀過而且這個array應該可以包含很多不同的值

作者: closer76 (克樓瑟) 2022-05-29 18:08:00

binary search 只要 O(log n)，而且不只 0/1 也可以做重點是 sorted

作者: Lipraxde (Lipraxde) 2022-05-29 22:37:00

量少的話可以用一些 bit operation 玩喔，LZCNT 之類的

作者: chchwy (mat) 2022-05-29 23:24:00

看到關鍵字sorted就知道是binary search啦

作者: hongsiangfu 2022-06-06 14:16:00

leetcode 34的需求很像

作者: wulouise (在線上!=在電腦前) 2022-06-06 22:38:00

std::uppwer_bound std::lower_bound看看很方便

繼續閱讀

[問題] 解題卡關password5353 [問題] atomic operation 與計算效率問題eagle32 [問題] 抽離IDE的工具鏈wei115 [閒聊] C++ LeetCode刷題的寫法hunter73419 [問題] cannot convert int (*)[size] to int*tarantula [問題] 一個演算法的問題bravooooo [問題] 有關 error: unknown type name 的問題datoguo [問題] 多線程及靜態變數的問題 su27 [問題] fprintf 導致 segmentation faulteagle32 [問題] implicit conversionManOfSteel