[LeetCode] Binary Searchable Numbers in an Unsorted Array

1966. Binary Searchable Numbers in an Unsorted Array

Consider a function that implements an algorithm similar to Binary Search. The function has two input parameters: sequence is a sequence of integers, and target is an integer value. The purpose of the function is to find if the target exists in the sequence.

The pseudocode of the function is as follows:

plaintext
1
2
3
4
5
6
7
8
func(sequence, target)
while sequence is not empty
randomly choose an element from sequence as the pivot
if pivot = target, return true
else if pivot < target, remove pivot and all elements to its left from the sequence
else, remove pivot and all elements to its right from the sequence
end while
return false

When the sequence is sorted, the function works correctly for all values. When the sequence is not sorted, the function does not work for all values, but may still work for some values.

Given an integer array nums, representing the sequence, that contains unique numbers and may or may not be sorted, return the number of values that are guaranteed to be found using the function, for every possible pivot selection.

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int binarySearchableNumbers(vector<int>& nums) {
int n = nums.size();
vector<int> r(n,INT_MAX), l(n, INT_MIN);
for(int i = 1; i < n; i++) {
l[i] = max(l[i-1], nums[i-1]);
}
for(int i = n - 2; i >= 0; i--) {
r[i] = min(r[i+1], nums[i+1]);
}
int res = 0;
for(int i = 0; i < n; i++) {
res += (nums[i] > l[i] and nums[i] < r[i]);
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/03/22/PS/LeetCode/binary-searchable-numbers-in-an-unsorted-array/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.

Related Issues not found

Please contact @SongHayoung to initialize the comment