The binary search idea sound interesting, but it is not always better.

I assume, you mean instead of iterating over the inner array, you binary search the point for each outer (boundaries for the binary search determined by the result of the previous search).

I would very rarely claim that a particular algorithm is _always_ better than another.

In his particular case, if (that's a big if) a binary search is applicable instead of a linear search, then the binary search will be faster even if the arrays have a dissimilar number of elements. What is critical is the number of elements, not the differential between the two.

For instance, with two arrays of 100 elements each, a linear search of one into the other will yield an average of 100 * 50 comparisons to do all the processing he needs to do. That is 5000 comparisons.

Using a binary search, doing the searches will need _at most_ 14 * 100 comparisons, that's a nice saving.

Now, if the arrays were only 20 to 30 elements each, I'd consider the speed improvement too small to justify the added complexity of a binary search compared to the simplicity of a linear search. (presuming his application only has to do the search once per execution.)

In the case you present of 100 elements in one array and 10,000 in the other. The 100 element array can be binary-searched in _at most_ 7 comparisons and the 10,000 element array in 14 comparisons. The choice of which array to search is easy to determine.

10,000 * 7 = 70,000 when searching the small array vs

14 * 100 = 1400 when searching the large array

and that is the worst case in both instances.

It's the number of elements in the arrays that is important not the difference in the number of elements between the arrays. Of course, as the above calculation clearly shows, the direction can be very important when the differential in the number of elements is substantial (more than double.)

Anyway, only the OP knows for sure if the binary search is applicable to the problem he is trying to solve but, if it can be used, it would result in a nice speed improvement.

Also, I would not use the result of any previous search. There is no need for that. Every search yields a value for the upper index and lower index (used in the binary search), the value of the indexes at the end of the search are sufficient to determine if there was a match and, if there wasn't a match, the two values (lower and upper) indicate where the not found values falls in. That _seems_ to be enough to calculate the value of the variables by using a simple multiplication for the result of that search accumulated onto the results of the previous searches (instead of 1 accumulation per element in the linear search.)

The OP will figure out if this could work for him.