0

Given a problem, How do we know if we have to apply binary search if the question has an integer? For some obvious reasons, we know if the problem contains a sorted array, we apply binary search there. But there are tons of questions that do not have an array and still, binary search is applicable.

ujzwalp
  • 13
  • 5
  • Can you please give examples of problems without an array and where binary search is applicable? – Stef Aug 25 '21 at 09:10
  • square root-https://leetcode.com/problems/sqrtx/ Arranging Coins-https://leetcode.com/problems/arranging-coins/ – ujzwalp Aug 25 '21 at 09:22
  • 1
    Does this answer your question https://stackoverflow.com/questions/540165/where-is-binary-search-used-in-practice – susanth29 Aug 25 '21 at 09:43
  • Sometimes you don't have an explicit sorted data structure to search in, but you have a **search space**. For instance, you might be looking for the solution of an equation in an interval. The interval is not an array, it's a "theoretical" space to search in, but you can still use binary search. – Stef Aug 25 '21 at 09:51
  • Those examples are *not* "binary search", rather the first is a simplified example of Newton's method and the second should *never* use any kind of search, binary or otherwise, but should just apply the quadratic equation to solve it. – RBarryYoung Aug 25 '21 at 14:55

2 Answers2

0

If you're searching for a value, and you can tell if a guess is too high or too low, then you can apply binary search to find the value.

Even the usual case of searching in a sorted array is like this -- we are searching for the index of the desired element in the array, and we can tell whether a guess is too high or too low, because the array is sorted.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
0

For the purpose of binary search, the sorted array just represents a function that maps an input, we call it index, to an output that's monotonically ordered (increasing or decreasing) in correlation with the input.

So it doesn't matter for binary search if the function is

f(x) -> return the element at index x in an array

or

f(x) -> return 2 * x, for integer x // an example of a monotonically ordered function
גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61