无序数组二分搜索：找不到的数

面经贴找不到了。大意是

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，版主@14417335 发的所有帖子，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

这个题目我发过面筋 orz
可以看这个：https://www.1point3acres.com/bbs ... 382&pid=3872585

这道题不难的, 能被二分查找的特点是所有左边的数都比它小而右边的都比它大。所以用两个数组记录左边的最大值和右边的最小值即可。两遍遍历O(n)

mhsasd 发表于 2019-4-2 12:01
节选自144大神的例子：
Given nums: [22, 92, 25, 16, 29, 15, 49, 22, 38, 61]
Can't find: [16, 49,  ...

我的方法确实有点逻辑漏洞，那就这么考虑。二分查找，每次减半对吧？一个target能被找到的条件是每次的二分后，你都得符合条件（你要么比middle值大，在右边，要么你比middle值小，我到左边去找你）用递归解决。这个思路总可以了吧？需要我贴代码吗？

我觉得面试的时候可以跟面试官讨论有没有重复值，如果没有重复值话， 我的方法肯定没问题

补充内容 (2019-4-2 14:55):
小伙伴觉得我的方法可行的话，加点大米哈 :)

chenchen628 发表于 2019-4-2 08:19
这题是不是可以直接对数组模拟一次没有target的二分搜索，但是不同于平时二分搜索的是，两边都搜，但是由之 ...

给个代码：
像楼上说的有几个需要clarify的地方，这个代码前提是是基于简单 (s+e)/2 二分查找，找到就停止。
输出的是找不到的数的下标。 如果需要输出具体哪些数字找不到，还要考虑有些数字出现多次，有些下标找不到有些下标找得到的情况，就需要最后过一遍数组，用一个hashset保存找不到的数。

1. 
   
2. #include <iostream>
   
3. #include <vector>
   
4. 
   
5. using namespace std;
   
6. 
   
7. #define INT_MIN 0x80000000
   
8. #define INT_MAX 0x7fffffff
   
9. 
   
10. class Solution {
    
11. public:
    
12.     vector<int> cantSearch(const vector<int>& nums) {
    
13.         vector<bool> canSearch(nums.size(), false);
    
14.         search(nums, 0, nums.size()-1, INT_MIN, INT_MAX, canSearch);
    
15.         vector<int> res;
    
16.         for (int i = 0; i < nums.size(); ++i) {
    
17.             if (!canSearch[i]) res.push_back(i);
    
18.         }
    
19.         return res;
    
20.     }
    
21.    
    
22. private:
    
23.     void search(const vector<int>& nums, int s, int e,
    
24.                 int min_val, int max_val, vector<bool>& canSearch) {
    
25.         if (s > e || min_val > max_val) return;
    
26.         int mid = (s + e) / 2;
    
27.         if (nums[mid] < max_val && nums[mid] > min_val) canSearch[mid] = true;
    
28.         search(nums, s, mid-1, min_val, min(max_val, nums[mid]), canSearch);
    
29.         search(nums, mid+1, e, max(min_val, nums[mid]), max_val, canSearch);
    
30.     }
    
31. };
    

复制代码

如果知道中位数，则左半部＞中位数和右半部＜中位数的数会找不到。
那么如何在O(n)时间内找到中位数，可以用两个堆来找，或者平衡二叉树也可以。

BridgeHUHX 发表于 2019-3-9 01:36
如果知道中位数，则左半部＞中位数和右半部＜中位数的数会找不到。
那么如何在O(n)时间内找到中位数，可以 ...

可能我的题目描述不清楚。加个例子吧。

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

写了个代码，请多给一些例子？我没看到这道题目

林微熙 发表于 2019-3-14 00:20
写了个代码，请多给一些例子？我没看到这道题目

1. 
   
2. 再加一个例子：
   
3. Given nums: [22, 92, 25, 16, 29, 15, 49, 22, 38, 61]
   
4. Can't find: [16, 49, 25, 92, 15]
   
5. 
   
6. 对于任意数组中的元素，如果用标准的二分法搜索搜索不到，就是最后答案的一员。当然下面的是测试代码，达不到楼顶要求的O(N)了。
   
7. 
   
8. for (int j : nums)
   
9.   if (Arrays.binarySearch(nums, j) < 0)
   
10.     System.out.println("Can't find " + j);

复制代码

BridgeHUHX 发表于 2019-3-9 01:36
如果知道中位数，则左半部＞中位数和右半部＜中位数的数会找不到。
那么如何在O(n)时间内找到中位数，可以 ...

用堆或者Balanced BST的时间复杂度就不是O(N)了，找中位数果断用Quick Select啊

这题应该还是要问清楚用哪一种二分法的代码，还有数组有无重复数字吧，用Python写了个test case自己测是没问题的，但因为我用的二分法边界定义和Java Builtin Binary Search用的不一样，结果稍有偏差

kaipeng21 发表于 2019-3-26 04:59
这题应该还是要问清楚用哪一种二分法的代码，还有数组有无重复数字吧，用Python写了个test case自己测是没 ...

我很同意你的看法