作者Kuba4ma ()
看板C_and_CPP
標題[討論] 給排序過的Array 用最少運算資源找值
時間Sat May 28 12:05:53 2022
各位大神好
本魯最近在準備某間IC廠的面試
在網路上找到這題考古題
題目如下
```
給一個sorted array(ex: a[5]={1,1,1,0,0})，請找出第一個0的位置，請使用能降低CPU
跟memory負擔的用量
```
我能想到的就只有用for loop掃過一遍而已
請問還有更好的方法嗎
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.241.82.35 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1653710755.A.F73.html
1F：→ lingege321: binary search 05/28 12:28
2F：→ lycantrope: 都sorted 就用binary search阿 05/28 12:29
對耶 居然沒想到XD 一直往Bit operation的方向想
3F：推 gozule: 知道array長度，可以把內容轉為整數直接查表 05/28 12:29
了解 感謝你
※ 編輯: Kuba4ma (111.241.82.35 臺灣), 05/28/2022 13:00:23
4F：→ TheOneisNEO: 樓上說的方法應該還是要O(n) 全部都讀過 05/28 22:00
5F：→ TheOneisNEO: 而且這個array應該可以包含很多不同的值 05/28 22:01
6F：推 closer76: binary search 只要 O(log n)，而且不只 0/1 也可以做 05/29 18:08
7F：→ closer76: 重點是 sorted 05/29 18:08
8F：→ Lipraxde: 量少的話可以用一些 bit operation 玩喔，LZCNT 之類的 05/29 22:37
9F：→ chchwy: 看到關鍵字sorted就知道是binary search啦 05/29 23:24
10F：推 hongsiangfu: leetcode 34的需求很像 06/06 14:16
11F：推 wulouise: std::uppwer_bound std::lower_bound看看 很方便 06/06 22:38