Clever Geek Handbook

Can binary search be / binary? Looking for a greedy algorithm?

I am reading various stuff about Binary Search and it is not clear to me, is it a greedy binary (which I don't like it) or, could it be a greedy algorithm with some specific implementation?

And if it can be greedy, how does it make sense? If a global optimum is obtained by choosing a local optimum without revising previous options, it cannot guarantee correct results for a binary search.

+3


source to share


2 answers


Let's say you are looking for the element at index 100 in the 8-bit range of values ​​(1-256). The following indexes will be considered during your binary search:

  • 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 see that at each step you are testing the most significant bit that has not been tested yet, and if it does not overflow the result, it is added to the partial solution until the final result is found.



Thus, the following characteristics of greedy selection can be specified:

  • There is a candidate set consisting of 8 bits of the found number.
  • A greedy choice, considering at each step the most significant bit not yet used.
  • Checking if this bit can be added to the final solution by looking at the bit locally and the result collected so far.
  • If the sum doesn't overflow this bit, it makes part of the final decision.
  • The final decision can be determined when the amount is equal to the desired one.

Of course, no backtracking is ever required, so this is the ideal greedy algorithm.

+2


source


I think if you look sideways at it, binary search is greedy in the sense that you are trying to reduce the search space as much as you want, at every step. It's just a greedy algorithm in the search space with a structure that makes it efficient and can always find the right answer.

I am not prone to squint.



Thus, binary search can be used inside the traditional greedy algorithm. For example, a greedy packing problem algorithm might ask you to select "the largest available item that can still fit." You can use binary search for this.

Conversely, the greedy algorithm can be used to create a data structure that works well for binary searches. See for example https://en.wikipedia.org/wiki/Geometry_of_binary_search_trees#Greedy_algorithm

+2


source






More articles:


All Articles