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

[Kuba4ma ()]

各位大神好

本魯最近在準備某間IC廠的面試

在網路上找到這題考古題

題目如下

```
給一個sorted array(ex: a[5]={1,1,1,0,0})，請找出第一個0的位置，請使用能降低CPU
跟memory負擔的用量
```

我能想到的就只有用for loop掃過一遍而已

請問還有更好的方法嗎

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.241.82.35 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1653710755.A.F73.html
→ lingege321: binary search
→ lycantrope: 都sorted 就用binary search阿
對耶 居然沒想到XD 一直往Bit operation的方向想

推 gozule: 知道array長度，可以把內容轉為整數直接查表
了解 感謝你
※ 編輯: Kuba4ma (111.241.82.35 臺灣), 05/28/2022 13:00:23
→ TheOneisNEO: 樓上說的方法應該還是要O(n) 全部都讀過
→ TheOneisNEO: 而且這個array應該可以包含很多不同的值
推 closer76: binary search 只要 O(log n)，而且不只 0/1 也可以做
→ closer76: 重點是 sorted
→ Lipraxde: 量少的話可以用一些 bit operation 玩喔，LZCNT 之類的
→ chchwy: 看到關鍵字sorted就知道是binary search啦
推 hongsiangfu: leetcode 34的需求很像
推 wulouise: std::uppwer_bound std::lower_bound看看 很方便