作者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/cn.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