# Tag Info

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 ...
• 9,837
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 ...
• 605
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 ...
• 4,416

### 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 ...
• 13.2k
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 ...
• 39k

### 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 ...
• 201
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 + ...
• 1,797
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 ...
• 1,198
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 ...

### 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 ...
• 29.5k

### 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) ...

### 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 ...
• 30.1k

### 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$ ...
• 160k

### 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 ...
• 13.2k
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 ...
• 29.5k
Accepted

• 4,817
Accepted

• 277k

### 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 ...
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 ...
• 831
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 ...
• 1,669
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 ...
• 29.5k
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 ...
• 277k
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 ...
• 39k