Re: Can Binary Search Be Improved with Threading

jehugaleahsa@xxxxxxxxx wrote:
Hello:

My boss suggested that he could write a faster binary search than I
could by creating a new thread and searching the data on each half on
the range. In other words, he would create a new thread to check the
other half of the range. I am assuming this is a binary search that
operates on contigious memory like an array, C++ vector, etc or in a
binary search tree.

Now, I thought this was rediculous but I kept it to myself. My
coworkers aren't trained programmers or Computer Scientists. As I saw
it, every time you split the list, you already know which way to go,
so why would you create a thread to check the other side? The overhead
of the thread is overkill, and one of the threads will always lead to
a dead end (it also destroys the invariant).

Am I in the wrong here, or is my boss' suggestion just plain wrong?


Maybe two threads, thread-0 searches the even indices, thread-1 the odd?

Shouldn't be too impressive. Binary search is O(log_2(n)), two threads have each O(log_2(n/2)) = O(log_2(n)-1). For twice the energy consumed this is a brouhaha.

In theory, you could take M processors to split the array up into M+1 search segments. If the processors are tightly coupled they would decide in each step which segment contains the result and jump onto it etc. That way you get O(log(n)/log(M+1)) if you can avoid the synchronization overhead.


.

Relevant Pages

  • Re: What is the best way to pull out a range of values?
    ... Then you can use binary search to find the first element above the lower ... That's exactly what binary search does, in log n time for lists of ... I don't know for sure if the "data" array is static or it is being ... int chkndx = pos; ...
    (comp.lang.perl.misc)
  • Re: Buggy BinarySearch implementation, real life and a curious soul...
    ... typical daily array size? ... So either roll your own binary search function, ... So my question's audience are people who had both CL and Java ... the Modula-2 language specifies that overflow errors are detected: ...
    (comp.lang.lisp)
  • Re: searching an array, string compare functions, string sorting
    ... array is not generated with JavaScript. ... When searching a word in the index, I do a quick binary search. ... exactly the way as JavaScript would sort them. ... Javascript sort can be given a user-written compare function, ...
    (comp.lang.javascript)
  • Re: Reading & Searching a Huge file
    ... then I think you could take advantage of the fact that the lines are all _almost_ the same length and do a binary search on the file itself. ... This is, I think, what you're suggesting when you wrote "read all the numeric values sequentially into some array"; you didn't mention also storing the file offsets for each record, but hopefully you realize that's implied since otherwise keeping the values in an array wouldn't be useful. ... keep in mind that this is the sort of thing that databases are really good at. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: fast dictionary search algorithm
    ... >> requested word's meaning in the shortest time possible. ... >Im no expert but I would have thought a binary search for a hash from ... using it as an array offset. ...
    (comp.programming)