2

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?

Gyuhyeon Lee
  • 878
  • 1
  • 9
  • 20
A. Szokalski
  • 65
  • 1
  • 6
  • 2
    please post some code, so we see what u have done. – Indraneel Bende Jan 20 '18 at 16:59
  • how often are you looking at the number? how big is/are the array/s? – Nina Scholz Jan 20 '18 at 17:04
  • btw, what means find? just a check if the number is in the array or the index? – Nina Scholz Jan 20 '18 at 17:09
  • Indraneel Bende The project I am currently working on is really big and not a lot is done yet. I am writting some pdfs to make everything clear (it will be open source so I kind of need to do that). I am planning things to not have to redesign everything later. That part of code havent been done yet because if there is no fast way to do this i will have to redesign everything. Later when I finish docs I will link them there. – A. Szokalski Jan 20 '18 at 17:32
  • See also [Why is using a loop to iterate from start of array to end faster than iterating both start to end and end to start?](https://stackoverflow.com/questions/47049004/why-is-using-a-loop-to-iterate-from-start-of-array-to-end-faster-than-iterating) – guest271314 Jan 20 '18 at 17:48
  • In real-life applications, inverted indexes are used for these sorts of things: https://en.wikipedia.org/wiki/Inverted_index – Matt Timmermans Jan 20 '18 at 19:07
  • What exactly is *n*? The total number of values, the average number of values in each array, or the number of arrays? Why did you say that divide and conquer is still *O(n)*? – trincot Jan 20 '18 at 23:54
  • no. Divide and conquer is O(log n). But I have many arrays here so I have to go through all of them fo in the end going through these arrays will be linear so O(n) – A. Szokalski Jan 21 '18 at 08:44

3 Answers3

2

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.
Gyuhyeon Lee
  • 878
  • 1
  • 9
  • 20
2

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.

guest271314
  • 1
  • 15
  • 104
  • 177
  • This is the correct solution, since Hashmaps provide O(1) for searches. However, I have a feeling that OP didn't want this approach - it feels like this is a question for a CS 101 exam, and hash implementations aren't what they're looking for when asking about finding numbers in linear arrays. – Gyuhyeon Lee Jan 20 '18 at 17:09
  • No it's not for exam really. I am working on project and I am stuck. I will send here some more info about this project later. Thanks for answer. – A. Szokalski Jan 20 '18 at 17:34
  • Ok i see i have to give you some more info. What we are talking about is a database in blockchain. The reason why there is so many arrays is because blockchain is made of blocks. Now if I want to create a map i would have to merge all arrays and it's O(n). Answer is good but not fitting my circumstances. Thanks for help. – A. Szokalski Jan 20 '18 at 17:40
  • @A.Szokalski What exactly is the requirement? – guest271314 Jan 20 '18 at 17:44
  • It has to find data in the database fast as fast as it would from normal database (ok maybe not that fast but you get the point). – A. Szokalski Jan 20 '18 at 17:57
  • @A.Szokalski "fast" is subjective. "fast" compared to? You can try using `Array.prototype.find()` – guest271314 Jan 20 '18 at 17:57
1

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)
nitte93
  • 1,820
  • 3
  • 26
  • 42