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
119
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
142
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
64
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
199
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,087
2
votes
1
answer
168
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
121
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
344
views
5
votes
1
answer
260
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,491
3
votes
1
answer
110
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
102
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
134
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,087
-1
votes
1
answer
113
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
600
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
191
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]
...
- 159
1
vote
0
answers
115
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', ...
