# Tag Info

## Hot answers tagged binary-search

87

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 respect to their asymptotic behavior. For example $$\log_{10}n = \frac{\log_{2}n}{\log_{2}10} = C \log_{2}{n}$$ where $C = \frac{1}{\log_{2}10}$. So $\log_{10}n$ ...

82

If you apply binary search, you have $$\log_2(n)+O(1)$$ many comparisons. If you apply ternary search, you have $$2 \cdot \log_3(n) + O(1)$$ many comparisons, as in each step, you need to perform 2 comparisons to cut the search space into three parts. Now if you do the math, you can observe that: $$2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)}... 32 DCTLib is right, but forget the math for a second. By your logic then, n-ary should be the fastest. But if you think about it, n-ary is exactly equal to a regular iteration search (just iterating through the list 1 by 1, but in reverse order). First you select the last (or next to last) item in the list and compare that value to your comparison value. Then ... 23 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 characteristics, Interpolation Search has expected run time of O(log(log(n)) assuming the data is uniformly distributed, however it pays for this by having O(n)... 17 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 search. 13 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 using signed integers. So instead they take the distance between left and right and add half of that to left. This is only a single extra operation to make the algorithm more robust. 10 I think most text book will provide you a good proof. For me, I can show the average case complexity as follows. Assuming a uniform distribution of the position of the value that one wants to find in an array of size n. For the case of 1 read, the position should be in the middle so there is a probability of \frac{1}{n} for this case For the case of 2 ... 10 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 + n \log n) = O(n^2)  The idea is that the linear work of shifting trumps the logarithmic work of comparing. You end up doing less comparisons, but still a ...

10

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 context. In pure mathematics, the base is almost always assumed to be $e$ (unless specified), while in certain engineering contexts it might be 10. In computer ...

9

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 space into two ranges - $[L,mid-1]$ and $[mid,R]$. The conquer step - Let's assume that WLOG the element $x$ that we are searching for is such that $x < A[mid]$. ...

9

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 that is either Comparable to itself or some superclass of itself (implementing Comparable) or can be compared with an outside tool (using a Comparator). But I ...

9

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 computational complexity. Run the binary search three times. At least two of the three results must be equal to the hidden number. Return the majority result. There ...

7

After viewing the original question, it seems that you have an additional piece of information: you know that the first element is 1 and that the last element is 0. This is crucial! So indeed you can solve it with binary search: first observe that if the first element is 1 and the last is 0, there must be subsequence of the form $1,0$ in the array. Denote ...

7

An iterative algorithm seems like it should work. Let $M=\lfloor N/4 \rfloor$. Suppose we know that $x$ is the integer approximation to $\sqrt{M}$, i.e., $x=\lceil \sqrt{M} \rceil$, and suppose we know the value of $x^2$ (obtained previously). Now we want to find $y=\lceil \sqrt{N} \rceil$. What are the possible values of $y$? I'm pretty sure the only ...

7

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 truth, this happens only once. I suspect you can do better. If the number is from 1 to 100 and I check the numbers 40 and 60 then knowing that one answer is ...

6

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 theoretically faster, interpolation search has two disadvantages compared to binary search: It has terrible (linear) worst case performance The overhead of ...

6

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$ and an algorithm that examines at most $c$ elements of the array, regardless of $n$. Then this algorithm can't possibly solve your problem. In particular, ...

6

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) would end up being junk since that big a number (131061) cannot be stored in a your 16-bit integer. And so, mid would be a wrong value.

5

but they, in the lecture, are saying that this algorithm involves 10 steps. Why? He says:"10 - give or take" in the lecture, which means that 10 is an estimate with a small uncertainty in either direction. He accepted it as estimate from the audience, which replies to his question, either because he couldn't be bothered to calculate the correct result or ...

5

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 and conquer is to split the original problem into smaller subproblems of a similar nature, and then combine them to deduce the final answer. In the case of ...

5

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 $O(log\ n)$ worst case time (values unevenly distributed): Introspective search is your method (iterating between an interpolation search and a binary search). ...

4

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 $n$ operations if the program does not know the depth beforehand or by some trickery, or the depth is not stored, say, in nodes. You are confusing three things ...

4

Now that the question has been edited to make it clearer what you are asking, there is a simple and elegant answer. The solution is: delta debugging. Delta debugging solves exactly this problem. Let me elaborate. Problem statement I am interpreting your question as asking about the following problem: We have $M$ software modules, and some way to run ...

4

Use your web browser. You can get the first 2 million or so digits in this link, and then use your browser's searching facilities. I was able to locate 351814 within the first 2 million digits (though not within the first 1 million digits, available in a separate link). By the way, I found both links on Wikipedia.

4

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 $\mathbf{O}$ with each vertex of the polygon and the vertices are ordered. To construct a binary search algorithm that determines in which wedge the point $\mathbf{z}$ ...

4

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 elaborate a bit, what you have is a binary search algorithm which works in $O(\log(n))$. What you want to prove is that any other algorithm for the same problem will ...

4

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 $A$, the idea is to perform binary search on the array $B$ of length $m$ in which $B[i]$ is the number of elements in $A$ which are at most $i$. If $B[i] \geq k$ ...

4

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 a region at the front or back of the list. Once you've bounded it you can just do a binary search. Can you see why this works?

4

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 indices $1$, $2$, $4$, $8$, $16$, $\dots$. Or with indices $1$, $3$, $7$, $15$, $31$, $\dots$. This way, it will take $O (\log k)$ steps to arrive at the first ...

4

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 one pair of consecutive elements modulo $n$ in $A$ will be "greater than" if $A$ is some circular shift of an increasing array (possibly the trivial shift by $0$),...

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