Search: binary vs. linear

[amarone]

Hello everybody, here I am with my new dilemma, trying to understand when binary search is actually cheaper then linear search. Hope it's not too stupid <scratches head>:

I have an array, ascending sorted by value, I must find out the index of the one element containing 50, out of 1,000,000.

Linear search works on 50 iterations (5,000,000 if I look for 5,000,000 value), as many comparisons and 1 return, null or the identified index.

Binary search needs 20 iterations on the array (2²⁰ = 1,048,576) and a repeated amount of php built-in functions to decrease the search area on the basis of as many comparisons; eventually, the return of the index (or null if not found, obviously).

Well, here is my doubt: if I count my code operations, it's easy to state that on average binary search is lighter then linear search; but what is the actual weight of all the comparisons, the assignments, the structures of the b.s. versus the single structure, the single comparison, the single assignment, the single return, all multiplied by the number of iterations needed by the l.s., keeping in mind everything lies under each of the built in functions?

One more element is to be considered: I don't know processing architecture of pc cpus and operating systems, but the same question based on an IBM AS400 would need an in-depth analysis because of it's way of processing linear operations. The AS bufferizes big chunks (of records of a file, of array elements, etc.) in its ram and then chews them one by one in big aggregate operations, speeding enormously the job and giving sense to my doubt.

Not an idle talk, i actually need to optimize my code because of the huge amount of data to be processed.

Thank you all!

Iacopo

[VGR]

given you can't intrumentalize the binary code in PHP, you've either to instrumentate your source code - that's tedious - OR - simplicity is queen - just do some benchmarking (performance measurements).

that'll tell you which technique is the best in worst/best/average conditions, depending on the test data

good luck

[GrandSchtroumpf]

It took me some time to understand the question.  We were missing some information.

This is how i understand the question:
We have a sorted array that contains 1,000,000 distinct positive integer values and we need to find the index of the value "50".
Since the array is sorted and has no duplicate values, we know that the index will be between 0 and 49.

AFAIK, PHP does not have optimized built-in search functions for sorted arrays (neither binary nor linear).
This means you"ll need to write your own search function.
Note that the "array_search" PHP function will traverse the complete array if the searched value is not in the array.

Your mistake is to only look at the max comparisons (50 for linear, 20 for binary on the whole array).
You also need to look at the typical number of comparisons, and that will depend on the typical content of your array.

What will be the typical index of your value "50"?
If it's close to 0, then do a linear search starting at index 0.
If it's close to 49, then do a backwards linear search starting at index 49.
If there is no typical index, do a binary search that is limited to the first 50 values of your array.

And as VGR said, benchmark the different algorithms inside your application.

Cheers.