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.

Answer 1

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