Skip to main content
87 votes
Accepted

Why is the log in the big-O of binary search not base 2?

When you change the base of logarithm the resulting expression differs only by a constant factor which, by definition of Big-O notation, implies that both functions belong to the same class with ...
fade2black's user avatar
  • 9,837
23 votes
Accepted

Can this algorithm still be considered a Binary Search algorithm?

I would not call this a binary search. It is clearly similar to binary search and it's natural to see it as a refinement of binary search. However it has significantly different algorithm complexity ...
Taemyr's user avatar
  • 605
22 votes
Accepted

Why is binary search using this weird thing to calculate middle?

Because left + right may overflow. Which then means you get a result that is less than left. Or far into the negative if you are ...
ratchet freak's user avatar
17 votes

Can this algorithm still be considered a Binary Search algorithm?

Yes, this is known as Interpolation Search. With some caveats (depending on your computational model and the distribution of the data) its expected running time is $O(\log \log n)$, better than binary ...
Tom van der Zanden's user avatar
17 votes
Accepted

"Guess the number" Problem on Turing machines

Yes, it is pointless and absurd to implement an algorithm to "guess the number" using the most common kind of Turing machine, whose head can read any cell on the tape, since, as you pointed ...
John L.'s user avatar
  • 39k
10 votes

Why is the log in the big-O of binary search not base 2?

In addition to fade2black's answer (which is completely correct), it's worth noting that the notation "$\log(n)$" is ambiguous. The base isn't actually specified, and the default base changes based on ...
MattPutnam's user avatar
10 votes
Accepted

Why is the time complexity of insertion sort not brought down even if we use binary search for the comparisons?

For the $j^{th}$ element, you would do ~ $\log j$ comparisons and (in the worst case) ~$j$ shifts. Summing over $j$, you get $$ \sum_{j = 1}^{n} (j + \log j) = \frac{n(n+1)}{2} + \log (n!) = O(n^2 + ...
aelguindy's user avatar
  • 1,797
9 votes
Accepted

Categorization of Binary search as Divide and Conquer

This might seem silly but here we go. Let our array be $A$ and the current range we are searching in be denoted as $[L,R]$ and let $mid = \frac{L+R}{2}$. The divide step - We divide our search ...
Banach Tarski's user avatar
9 votes
Accepted

How binary search works in real world scenario?

As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes. At least in Java, all we need is data ...
Benny Profane's user avatar
9 votes

Find the number using binary search against one possible lie

A generalization of this class of problems is widely studied. See, e.g., this paper for a survey. In your particular case, the problem can be easily solved without any asymptotic change in the ...
Steven's user avatar
  • 29.5k
8 votes

Why is binary search using this weird thing to calculate middle?

Suppose your 'low' and 'high' are 16 bit unsigned integers. That means, they can only have a maximum value of 2^16=65536. Consider this, low = 65530 high = 65531 If we added them first, (low+high) ...
Bikash Gurung's user avatar
7 votes

Find the number using binary search against one possible lie

If normal binary search would take k questions, then you can solve this with 2k+1 questions: Ask each question twice. If you get the same answer, it was the truth. If not, a third question reveals the ...
gnasher729's user avatar
  • 30.1k
6 votes

Finding a value in a sorted array in log R time, R is the number of distinct elements

There is no such algorithm. Here's an information-theoretic proof that it can't be done, inspired by gnasher79's answer. Let's focus on the special case where $R=3$. Suppose there is a constant $c$ ...
D.W.'s user avatar
  • 160k
6 votes

Is there any study or theory behind combining binary search and interpolation search?

Interleaving two algorithms to get the best of both worlds is a known technique, though it is usually stated as running them in "parallel" and returning an answer as soon as either terminates. Though ...
Tom van der Zanden's user avatar
6 votes
Accepted

how can turing machines be universal models of computation if they can't perform binary search?

Turing Machines can simulate binary search, in the sense that they can compute whatever you can compute using binary search. You seem to be confusing computability and complexity, which are two ...
Steven's user avatar
  • 29.5k
5 votes
Accepted

Is there any study or theory behind combining binary search and interpolation search?

Have I stumbled across a known thing? There are various methods, based on a mix of interpolation-search and binary search, with a $O(log\ log\ n)$ average case access time (uniform distribution) and $...
manlio's user avatar
  • 2,062
5 votes

Categorization of Binary search as Divide and Conquer

There is no accepted formal definition of the divide and conquer paradigm (see this question for some suggestions), and so we must regard this paradigm as an informal concept. The main idea in divide ...
Yuval Filmus's user avatar
5 votes

"Guess the number" Problem on Turing machines

In casual words, a Turing machine can do anything computational, but nothing else; especially there's no IO. No keyboard, no mouse. It just takes a tape as input and runs a predefined program on it. ...
Bubbler's user avatar
  • 406
4 votes
Accepted

Prove that the depth function of a Binary Search Tree is $O(\log n)$ on average

If your input binary search tree is like the one given below then no matter what the program does, the depth function will return $n-1$ (because the depth is $n-1$, in this case). And it will take $...
Sarvottamananda's user avatar
4 votes
Accepted

The use of binary search when determining whether a point lies inside a given convex hull

So, the situation is that you have the vertices $\mathbf{v}_i$ of a polygon that defines a convex hull and a point $\mathbf{O}$ inside this polygon. Furthermore you have the vectors connecting $\...
Gregor Michalicek's user avatar
4 votes
Accepted

Best Algorithm for searching for an index in an array such that A[i] = i

Notice that the index of the element of the array requires $\Omega(\log(n))$ bits to represent. This means that there can be no better algorithm than $O(\log(n))$ to find this index. Edit: To ...
cirpis's user avatar
  • 156
4 votes

Understanding Binary Search for Kth Smallest element in an Array

Let me start by recalling the question: Given an unsorted array of $n$ elements in the range $1,\ldots,m$, find the $k$th smallest element in $O(n\log m)$ time and $O(1)$ case. Calling the array $...
Yuval Filmus's user avatar
4 votes

Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))

Check the first element. Then check the last. Then the second, then the second to last, then the fourth, then the fourth to last, then the eighth, and so on. Stop upon bounding the location of x to ...
Daniel McLaury's user avatar
4 votes
Accepted

Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))

The basic idea, when we don't know $k$, is to ask for elements with an exponentially growing index. The most natural here is some use of powers of two. For example, we can ask for elements with ...
Gassa's user avatar
  • 831
4 votes
Accepted

Finding an interval in a binary search tree that contains a point

You can't find a better algorithm for your problem using comparisons, because a lower bound of $\Omega(\log n)$ can be proven for these setings (proof below). What you can do is some minor ...
lox's user avatar
  • 1,669
4 votes
Accepted

Is there a O(log n)-time algorithm to find the maximum element of a circular shift of a sorted array?

Let $A = \langle a_1, \dots, a_n \rangle$ be the input array. I will only consider the case $n \ge 3$, otherwise the problem is trivial. The key property is that the order relation between all but ...
Steven's user avatar
  • 29.5k
4 votes
Accepted

Theoretical lower bound of finding number of occurrences of a target integer in a sorted array

The problem requires $\Omega(\log n)$ accesses to memory even if you are promised that the target integer appears at most once. You can prove it using an adversary argument. Say that the target is ...
Yuval Filmus's user avatar
4 votes
Accepted

Binary-ish search through partially ordered set

Here is a simple algorithm that runs in $O(N^2)$ time and $O(N)$ space, assuming that $f(\emptyset)$, $f(\{1\})$, $f(\{2\})$, $\cdots$, $f(\{N\})$ are given in an array. The starting idea is about the ...
John L.'s user avatar
  • 39k
4 votes
Accepted

Find out if a path exists avoiding circular obstacles

Your assumption using binary search is a good assumption, that means that we can assume we know the radius, and focus only on the subproblem: Given a rectangle and a set of circles, is it possible to ...
Pål GD's user avatar
  • 16.1k

Only top scored, non community-wiki answers of a minimum length are eligible