Can Binary Search be / Is Binary Search a greedy algorithm?

Question

I'm reading different materials about Binary search, and it's not clear to me is it a greedy binary (which looks to me like it's not) or, CAN it be a greedy algorithm with some specific implementation?

And if it can be greedy, how it make sense? If the global optimum is obtained by selecting the local optimum, without reconsidering previous choices, it can't guarantee correct results for the binary search.

Oppressive

Answer 1

Consider you are looking for an element at index 100 in a 8 bit value range (1-256). Your binary search progress will consider following indices:

• 128 ? Too big
• 64 ? Too small
• 64 + 32 ? Too small
• 64 + 32 + 16 ? Too big
• 64 + 32 + 8 ? Too big
• 64 + 32 + 4 ? Found

It is easy to to notice that in every step you are testing the most significant bit not tested yet and if it does not overflow the result it is added to the partial solution until the final result is found.

So following characteristics of the greedy choice can be pointed:

1. There is a candidate set composed of 8 bits of the number to find.
2. Greedy selection considering in every step the most significant bit not used yet.
3. Checking if that bit can be added to the final solution locally looking at the bit and the result assembled so far.
4. If the sum does not overflow that bit makes part of the final solution.
5. The final solution can identified when the composed sum is equal to the searched one.

Of course no backtracking is ever needed so this is a perfect greedy algorithm.

Photostat

Yes, in a way binary search is a greedy algorithm, but in another, more accurate way, it's not. – Giorgi

Hmm. Interesting, thanks. Is there a more precise definition for that? – Oppressive

@Stas This is not formal. More like replacing the idea of throwing away half of the input in binary search by adding up bits representing the final number. That finally could achieve the same goal (log(n) and even trying the same indices) while strictly meeting the expectations for a greedy algorithm. Of course some adjustment to make the input size a power of 2 may be needed. Another issue is that binary search does not even assume that numbers are composed of bits. But those two approaches still have something in common. – Photostat

Answer 2

I guess if you squint at it sideways, binary search is greedy in the sense that you're trying to cut down your search space by as much as you can in each step. It just happens to be a greedy algorithm in a search space with structure making that both efficient, and always likely to find the right answer.

I don't tend to so squint.

That said binary search can be used inside of a traditional greedy algorithm. As an example, a greedy algorithm for a packing problem could ask you to next choose "the largest available item that can still fit". A binary search could be used to find that.

Conversely a greedy algorithm can be used to create a data structure that is well-suited to binary search. See for example https://en.wikipedia.org/wiki/Geometry_of_binary_search_trees#Greedy_algorithm

Prestissimo