0

I'm not a math person. My question sounds vague so an example is probably better.

I have a large list of arrays. Here's 3: 

2: [[64, 126, 188, 251, 313, 375, 437, 499, 562, 625, 695, 757, 824, 897, 961, 967]] 
3: [[64, 66, 127, 189, 251, 314, 376, 438, 500, 564, 626, 686, 696, 758, 821, 825, 891, 897, 957, 967]]
4: [[64, 66, 126, 190, 253, 313, 377, 439, 501, 564, 627, 697, 759, 826, 899, 968]]

Index 2 and 3 have duplicates of 64, 251, 897, 967 Index 2 and 4 have duplicates of 64, 126, 313 Index 3 and 4 have duplicates of 64, 66, 564 Index 2,3,4 has 64

If there's more index associated then let's give it a score of 10. Then compare the number of values within the index. 2, 3, 4 only has 64, but index 2 and 3 has 4 values, so let's give that a 9. So the more index number the better, then sort by the number of value by index.

What is the best way to go through each array without looping? Looking at thousands of array.

hammies
  • 103
  • 3

1 Answers1

1

It looks like all of your arrays are sorted. This means that it is very quick to search for a specific element in any array.

It can be done in $O(\log n)$ using a binary search.

Suppose you want to find $437$ in your first array, which has length $16$. First, you should check whether $437$ is in the first half of the array or the second half of the array.

  • Compare $437$ (the entry you wish to find) with $499$ (which is the $8^\text{th}$ entry). Since $437$ is less than $499$, the entry you want to find is in the first half of the array.

  • Compare $437$ (the entry you wish to find) with $251$ (which is the $4^\text{th}$ entry). Since $437$ is greater than $251$, the entry you want to find is in the second half of the first half of the array.

  • Compare $437$ (the entry you wish to find) with $375$ (which is the $6^\text{th}$ entry). Since $437$ is greater than $375$, the entry you want to find is in the second half of the second half of the first half of the array.

At this point, you know that $437$ appears after the $6^\text{th}$ entry and before the $8^\text{th}$, so you can deduce that it must be the $7^\text{th}$ entry.

Using a binary search allows you to avoid looping over the entire array.

Zubin Mukerjee
  • 17,832
  • wait so I'd need to do a binary search through every single array, wouldn't still be going through the entire list? like the first search still needs to find through second, third, fourth, fifth, etc – hammies Aug 11 '17 at 15:01
  • @JamAndJammies Yes, you would have go to through the entire list of arrays. Are the arrays related in some way? If they aren't, then you don't know anything about the second array from just looking through the first. So you have to search through each, independently. – Zubin Mukerjee Aug 11 '17 at 15:13
  • The arrays aren't related. That's what i was afraid of. thanks! – hammies Aug 11 '17 at 15:26