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

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

mooc 发表于 2019-3-31 11:08
这道题不难的, 能被二分查找的特点是所有左边的数都比它小而右边的都比它大。所以用两个数组记录左边的最大 ...

实现了一下不对的。并不是所有的能找到的元素都一定要满足这个条件。

这题是不是可以直接对数组模拟一次没有target的二分搜索，但是不同于平时二分搜索的是，两边都搜，但是由之前执行过的搜索决定现在正在查看的数是不是valid。最后每个数只会被access一遍，所以是On。

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. };
    

复制代码

mhsasd 发表于 2019-4-2 04:55
实现了一下不对的。并不是所有的能找到的元素都一定要满足这个条件。

请举个例子

mooc 发表于 2019-4-2 10:31
请举个例子

楼主在3楼的例子就行，[ 2, 7, 9, 10, 1 ]
这个例子里9是可以被查找到的，但是9右边有1比他小。

chenchen628 发表于 2019-4-2 11:37
楼主在3楼的例子就行，[ 2, 7, 9, 10, 1 ]
这个例子里9是可以被查找到的，但是9右边有1比他小。

题目里有一定能被找到的意思吧？

mooc 发表于 2019-4-2 10:31
请举个例子

节选自144大神的例子：
Given nums: [22, 92, 25, 16, 29, 15, 49, 22, 38, 61]
Can't find: [16, 49, 25, 92, 15]

用你建议的方法没有一个找到。满足你的方法一定可以找到那个元素 但是并不是只有这样才可以找到那个元素。因为二分法找的时候跳了很多元素。

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):
小伙伴觉得我的方法可行的话，加点大米哈 :)

可以求一下這題的python代碼嗎？