CODEWITHSUNDEEP
javascriptarraysalgorithm
A. Szokalski
A. Szokalski

Reputation: 65

How to find a number in many sorted arrays of numbers?

I have multiple arrays of various numbers.
There are no duplicate numbers across all of the arrays. The arrays can be sorted and it won't collide with my project.
How do I find a specific number in these arrays efficiently?
Is it possible to do it better than divide and conquer on every array (It would still be O(n) because you have to go through all of the arrays and there is a lot of them).
So is there a better solution?

Upvotes: 2

Views: 303

Answers (3)

nitte93
nitte93

Reputation: 1840

Lets say you have n sorted array.

To achieve the best case of finding a number in these array, will cost you o(NlogN) for merging them all and create a master sorted list, and then applying the binary searchO(logN).

Step 1: combine these arrays in sorted manner to get the master array.

Step 2: Apply binary search to find your element

Example: With two arrays: [1,2,3] and [4,5,6]

Step:1

let sortedMaster : [1,2,3].concat([4,5,6]).sort(function(a,b){return a - b});

Step: 2

sortedMaster.indexOf(yourNumber)

Upvotes: 1

guest271314
guest271314

Reputation: 1

Since the values (numbers) are all unique you can create a Map and populate the key, value pairs with the value then use Map.get() to retrieve the value.

Upvotes: 2

Gyuhyeon Lee
Gyuhyeon Lee

Reputation: 878

Finding a number in a list(array) is always O(n) when the numbers are random.
However, if the array is sorted, you can use binary search to find the number in O(log n).
See : https://en.wikipedia.org/wiki/Binary_search_algorithm
If you try binary searches in all each of the arrays, it will still give O(log n) given than n is the length of elements in all the arrays. 

Find "10"

1 3 5 8 9 10 14
      p
-> 10 is higher than p(pivot) 8, so remove the left part, and select pivot again

9 10 14
  p
-> 10 is equal to p 10. End search.

Upvotes: 2

Related Questions