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.
145 questions
0
votes
0
answers
137
views
Closed-form for exact number of iterations of binary search
Consider a sorted list of $n$ elements $x_1, \ldots, x_n$. Using binary search to find $x_k$ in this list takes $f(n, k)$ iterations, where $f : \mathbb{N}^2 \to \mathbb{N}$ is a function such that, ...
- 103
1
vote
2
answers
174
views
Picking high index for binary search of sorted array
The following pseudocode returns index of the given element x within sorted array A where p ...
- 15
0
votes
0
answers
72
views
What algorithm should be used to find the closest set of dates?
I have tried to outline my problem as structured as possible, here is a rough overview, I am trying to find the best matching stay for a hotel booking system. If someone inputs check in and checkout ...
- 101
1
vote
1
answer
208
views
Finding the smallest root
We are given an array $a$ of $n$ integers, such that the difference between each element $a[i]$ and the adjacent elements $a[i-1]$ and $a[i+1]$ is at most $1$.
Define a root of $a$ as an index $k$ in $...
- 6,131
2
votes
1
answer
230
views
Maximum of a tritonic array
I have found out how to find the maximum of a "bitonic" array. The problem is as follows.
An array is bitonic if it is comprised of an increasing or decreasing sequence of integers followed ...
- 121
1
vote
1
answer
125
views
Proof of correctness for Binary Search algorithm to find length of array for unknown length
For the algorithm provided in answer to this question, how would I go about proving the correctness of the algorithm?
The referenced question is:
“You are given an array $A$ of length $n$. Each value ...
- 91
1
vote
1
answer
389
views
5
votes
1
answer
313
views
"Unbounded" binary search in $\log_2(n) + O(?)$ comparisons
Binary search is the well-known algorithm that compares the input value to an entry in a sorted array, and based on the result then decides to check the same input value against another entry either ...
- 2,511
3
votes
1
answer
132
views
Time complexity of an uneven binary search
I have a concept binary search which doesn't split at the midpoint of a list, but at a ratio of 1:2.
If we abstract the search function time complexity into $T(n)$ then the function can recurse into ...
- 43
0
votes
1
answer
111
views
Number of steps of binary search given a stopping criterion
Reading a paper, I have found an algorithm that uses binary search to find a number between $0$ and $n\in\mathbb{N}$. The stopping criterion for this binary search is that $t_2-t_1<\frac{1}{k^2}$ ...
- 167
2
votes
1
answer
143
views
Finding an approximate double-zero using binary search
Let $f$ be a continuous real function on $[-1,1]$. The function is accessible via queries: for any $x$, the value of $f(x)$ can be computed in constant time.
If $f(-1)<0$ and $f(1)>0$, then by ...
- 6,131
-1
votes
1
answer
131
views
Inequality about External path length
First of all LPL is Leaf path length & IPL is internal path length. While i was studying algorithm analysis for average complexity of binary search , i saw that inequality. Before that, i proved ...
- 25
0
votes
1
answer
778
views
Guessing number game "hot" or "cold"
I thought up this problem and am trying to come up with an optimal solution.
I am thinking of a number uniformly randomly between 1-100, inclusive.
If you guess the number, you "win".
Else ...
- 11
1
vote
3
answers
208
views
Find the largest possible number not larger than some integer N and is the product of K consecutive primes
Source: Hanoi student competition of unknown year (Kì thi học sinh giỏi thành phố)
Additional conditions:
N is a positive integer in range [1, 2^64 - 1]
K is a positive integer in range [3, 10]
...
- 179
1
vote
0
answers
119
views
Unusual version of a binary search algorithm
For one dimensional, continuous binary search most effective algorithm would remember boundaries.
For example if boundaries are 0.7 and 0.9, point to check would be 0.8. And if result is 'too small', ...
