Questions tagged [binary-search]

Questions about the binary search algorithm, which can be used to find elements of an ordered list in O(log n) time.

Filter by
Sorted by
Tagged with
56
votes
3answers
27k views

Why is binary search faster than ternary search?

Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space. If, instead, we used 'ternary search', we'...
36
votes
2answers
14k views

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

I am new to understanding computer science algorithms. I understand the process of the binary search, but I am having a slight misunderstanding with its efficiency. In a size of $s = 2^n$ elements, ...
14
votes
3answers
3k views

Can this algorithm still be considered a Binary Search algorithm?

While doing the second code kata (which asks you to implement a binary search algorithm five times, each time with a different method), I've come up with a slightly different solution which works as ...
14
votes
3answers
749 views

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

I just read Can this algorithm still be considered a Binary Search algorithm? and recalled that a few years back I wrote an indexer/search for log files to find log entries in large plain text files ...
11
votes
6answers
1k views

Find the number using binary search against one possible lie

We all know this classic problem, "there is some hidden number and you have to interactively guess it.", which could be solved using binary search when we know that maximum number that we can guess. ...
10
votes
2answers
6k views

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

I noticed that in many books calculation of midpoint for binary search uses this: int mid = left + (right - left) / 2; Why not use ...
8
votes
3answers
4k views

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

There are two factors that decide the running time of the insertion sort algorithm: the number of comparisons, and the number of movements. In the case of number of comparisons, the sorted part (left ...
8
votes
4answers
6k views

Compute square root using (bit) additions and shifts as primitives

Question: Given an $n$-bit natural number $N$, how to compute $\lceil \sqrt{N} \rceil$ using only $O(n)$ (bit) additions and shifts? The tip is to use binary search. However, I could not achieve the ...
7
votes
1answer
29k views

Proving that the average case complexity of binary search is O(log n)

I know that the both the average and worst case complexity of binary search is O(log n) and I know how to prove the worst case complexity is O(log n) using recurrence relations. But how would I go ...
6
votes
1answer
147 views

Binary-ish search through partially ordered set

I have an interesting function. It takes subsets of {1,...,N} to positive integers, i.e. $f:P([N]) \rightarrow Z^+$. I know that if S is a subset of S', $f(S) < f(S')$. Also, if S and S' have the ...
6
votes
1answer
909 views

Optimize binary search on Segment Tree by storing past result

Goal Let $A[n]$ be an arbitrary array of integers of length $n$. Let $S$ be a segment tree, represented by an array of records: each record containing the left and right bounds ($[l,r]$) of the ...
5
votes
4answers
458 views

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

The standard binary search algorithm gives log N time, where N is the total number of elements in the array. When the array has duplicates, I don't see how you could detect those duplicates ahead of ...
5
votes
1answer
294 views

Fastest search algorithm in a sorted list with certain error rate-limiting constraints

This problem came up during the Google CTF 2017. For background information about the challenge you can search for GoogleCTF A7 ~ Gee cue elle. Problem description:...
4
votes
3answers
2k views

Categorization of Binary search as Divide and Conquer

Why do we call binary search as 'Divide' and 'Conquer' strategy? It does not combine the results unlike other Divide and Conquer strategies.
4
votes
1answer
3k views

How binary search works in real world scenario?

In binary search, we need an array of integers for it to search for an element. Also, many other sorting algorithm sorts array of integers. But in real world, we may search for a name of an employee ...
4
votes
2answers
385 views

Binary search with alternative comparison cost

I have a sorted array $A$ of non-arbitrary elements. Now, I have another element $c$ and I want to find out where it belongs in the sorting of $A$. The cost of comparing $c$ to $A_i$ is $\Theta(i^2)$. ...
4
votes
2answers
2k views

first intersection of two arrays of integers - double binary search feasible?

I'm interested to find the fastest possible way to find the first element of an intersection of two integers arrays (first match) Looking for the 'fastest' algorithm I have seen different methods ...
4
votes
1answer
262 views

lower bound for Renyi–Ulam Game with lies

Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ). Game : $A$ chooses an element in {1,2....,n} $B$ tries to ...
4
votes
1answer
209 views

Proving O(log n) bound for the number of iterations when we select the average as the pivot

Motivation So the other day I had fun providing a new solution to this famous question. In the analysis part I showed that my little algorithm has space complexity: ...
4
votes
1answer
3k views

Potential method for dynamic binary search

I'm trying to solve 17-2(b) problem from Cormen(CLRS) using potential method. Problem from Cormen: 17-2 Making binary search dynamic Binary search of a sorted array takes logarithmic search time, ...
4
votes
1answer
186 views

Searching a value in a "piecewise" ordered array

If we have an array $A$ of length $N$, which is partitioned into $\sqrt{N}$ adjacent subarrays $A(i)$, each of which is monotonically ordered from $\min(i)$ to $\max(i)$ (it is known what places have ...
3
votes
3answers
603 views

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

Given a sorted array $A[1,\ldots,n]$ and element $x$ that located at position $k$. We know $x$, we don't know $k$. Write an algorithm that finds $k$, in $O(\min(\log k, \log(n-k))$ time complexity. ...
3
votes
1answer
126 views

Finding a '1' cell with a '0' to its right in a binary array

Given an array of size n that holds ones and zeros I need to find an index of a 1 cell that has 0 to his right (in then next ...
3
votes
3answers
258 views

Minimum number of tests to identify subset of modules that trigger a bug?

I have an ordered set of $M$ software modules compiled together. The interaction of some $N$-tuple of these modules is causing a bug when the program is run. I can run the program with any desired ...
3
votes
2answers
347 views

Binary search uneven split number of queries?

For even split binary search (repeated halving) number of queries is log with base 2. According to Skiena's Algorithm Design Manual, if the split in binary search is by ratio 1/3:2/3 instead of 1/2:1/...
3
votes
1answer
85 views

Finding the number of $L\leq j\leq R$ such that $a[j] \leq a[i]$

I have recently encountered the following problem which I heard can be solved by using BIT (binary indexed trees) but I am not sure how: Given an array $a[1, 2, \ldots, n]$ and $Q$ queries of the ...
3
votes
1answer
71 views

Finding $k$-th element in prefix of size $i$

Let's say we are given array $A$ of size $n$. We need to answer some numbers of queries. For each query we are given index $i$ and integer value $k$, $k \le i$. If we take the first $i$ elements of ...
3
votes
2answers
290 views

Invariant on "Find K Closest Elements" problem

I run across this problem: Given a sorted array, two integers k and x, find the k closest ...
2
votes
1answer
60 views

Find out if a path exists avoiding circular obstacles

Given a rectangle defined by its corners $(0, 0)$ and $(w,h)$, $n$ circles $\{ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ with the same radius $r$, I need to determine the smallest possible radius r ...
2
votes
2answers
137 views

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

Consider this problem: You are given an array $A$ (of distinct integers) of one out of the following four types: Ascending (e.g., 1,2,4,6); Descending (e.g., 6,4,2,1); Ascending rotated (a non-...
2
votes
1answer
872 views

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

In an answer to the problem of determining whether or not a point lies inside a given convex hull, a thesis is mentioned, which says : For repeated queries with preprocessing allowed, we develop a ...
2
votes
2answers
4k views

How exactly Hashing performs better than a Binary Search?

The time complexity of a Binary Search is O(log n) and Hashing is O(1) - so I've read. I have also read that Hashing outperforms Binary search when input is large, for example in millions. But I see ...
2
votes
1answer
2k views

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

I am struggling with this question because I am not sure how to see that a depth function is $\mathcal{O}(\log n)$ on average when it clearly traverses through the whole tree which should make it $\...
2
votes
1answer
54 views

Extend binary search

There is a way for finding K entries of N given entries using a binary search? I mean, I have N entries, indexed from 0 to $N-1$ and I have to find $K$ of them that satisfy some constraint. The ...
2
votes
1answer
445 views

Searching a sorted array to find the $k$ closest values to a target value $T$

Let $A$ be a sorted array of $N$ values. I am interested in finding the index $j$ such that the elements $A_j, A_{j + 1}, ..., A_{j + k - 1}$ have the $k$ closest values to the given target value $T$. ...
2
votes
1answer
100 views

Approximation with imperfect dichotomy oracle

Given an unknown $x$ and an oracle $O(r)$ such that: If $O(r)$ is true then $x \geq r$. If $O(r)$ is false then $x < 2r$. Conversely, the oracle has a defined behaviour only outside the interval $...
2
votes
1answer
46 views

How can we prove that in binary search, low – high ≤ 1

How can we prove that in binary search $$\mathit{low} - \mathit{high} ≤ 1$$ Below is a sample algorithm for Binary Search. ...
2
votes
1answer
105 views

Determine whether a sorted array contain at least 4 distinct elements in O(log n) time

On one of my previous courseworks, I was faced with the following problem, which I think is unrealistic when using a direct / straightforward approach that usually algorithms have by leveraging ...
2
votes
1answer
69 views

Finding pair of sum in sorted array in time complexity less than $O(n)$

In a sorted array, I am trying to find just one pair that sum up to a certain value. I was wondering if anyone could help me improve my code in performance or memory. I know the code which is $O(n)$. ...
2
votes
1answer
44 views

Error in pivot selection algorithm for merge phase [Sorting]

In the paper Comparison Based Sorting for Systems with Multiple GPUs, the authors describe the selection of a pivot element with respect to the partition on the first GPU (and its mirrored counterpart ...
2
votes
1answer
81 views

Efficient search algorithm for a monotonic boolean array wherein the probability of target's location is available apriori

A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$. $$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in ...
2
votes
1answer
69 views

Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function

A boolean-valued function defined in the set of positive integers, $\mathcal Z$. $$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in \mathcal Z $$...
2
votes
1answer
310 views

Worst case runtime for binary search

The run time of binary search is O(log(n)). log(8) = 3 It takes 3 comparisons to decide if an array of 8 elements contains a given element. It takes 4 comparisons in the example below. python2.7 <...
2
votes
1answer
639 views

number of comparisons in searching algorithms

i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these. For linear search : ...
2
votes
1answer
588 views

In which situation do we choose randomized binary search instead of the normal binary search?

Both randomized and normal binary search takes O(log n) time complexity but why does the randomized version exist? In other words what is the advantage of randomized binary search even if it has same ...
2
votes
1answer
2k views

Finding median of three sorted array (the same length)

I think about following problem: There are given three sorted arrays $A,B,C$ (each of them is length $n$). Every array has distinct elements. Find median of union $A,B,C$. I consider following ...
2
votes
1answer
135 views

Find number of triples that sum up to zero in query-intervals

My problem is that we have an array of $N$ integers $(N <=5000)$ on the interval $[-10^6,10^6]$. We also have $Q$ queries $(Q <= 10^5)$ giving us some range in the array. For each query, we ...
2
votes
0answers
409 views

Understanding the behaviour of different variations of Binary Search

Binary Search is a fairly simple and standard algorithm that can be used (among other things) to find a target element in a sorted array. There are subtle variations in code to do this, however all of ...
2
votes
1answer
38 views

Smallest segment after whose removal all elements are distinct

I am interested in the following problem: We are given an array of integers and we need to find the size of smallest subsegment such that after removing it all elements in the array are distinct. ...
2
votes
0answers
56 views

Two flavors of red-black trees with different performance

I've implemented two red-black trees (using the pseudo-code in CLRS) with slightly different flavors: 1) In the first tree, all the data is stored in the leaves. 2) In the second tree, the data is ...