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
132
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
0
votes
0
answers
65
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
2
votes
1
answer
178
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
349
views
3
votes
1
answer
111
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
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
0
votes
1
answer
612
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
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', ...
3
votes
1
answer
103
views
optimal search algorithm for finding parameters and thresholds
I have the following problem:
There are $n$ variables $x_i$, $i=1...n$, each can take integer values from 1 to $m$. For every set of values I can run a test which has a binary outcome ('Pass' or 'Fail'...
- 31
0
votes
0
answers
112
views
Binary search with mid index equals to $\frac{(right + left )}{2}$
I have tried to implement traditional binary search on an array. Now, if I set the mid index to be $mid = \frac{(right + left )}{2}$, my code does not run within time quota specified already, however, ...
- 553
4
votes
6
answers
2k
views
"Guess the number" Problem on Turing machines
I am currently learning about the concept of Turing Machines and trying to relate it with my knowledge on the application of the Binary Search algorithm.
The problem I am working on is to write an ...
- 61
2
votes
2
answers
2k
views
Split the given array into K subsets such that maximum sum of all subsets is minimum
Given an array of $N$ elements, $A$, and a number $K$. ($1 \leq K \leq N$) .
Partition the given array into $K$ subsets (they must cover all the elements but can be noncontiguous too). The maximum ...
- 260
0
votes
1
answer
332
views
Greedy approach behind SPOJ Aggressive Cows problem
My doubt is related to the given SPOJ problem:
Farmer John has built a new long barn, with N (2 <= N <= 100,000)
stalls. The stalls are located along a straight line at positions
x1,...,xN (0 &...
0
votes
1
answer
502
views
while(l < r) vs. while(l <= r) advantages/disadvantages in binary search
There many many ways to code binary search, but one of the main distinctions I've seen in people's code is one group of people use while(l < r) and another uses <...
- 123
-1
votes
1
answer
152
views
how can turing machines be universal models of computation if they can't perform binary search?
I have searched around and it seems like it is impossible for a Turing machine to implement binary search for an arbitrary sized array. How can a turing machine be called universally computable if it ...
- 123
2
votes
1
answer
128
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.
...
- 147
1
vote
1
answer
3k
views
Upper and lower tangent line to convex hull from a point
Is it possible to find an upper and lower tangent line to a convex hull in $log(n)$ time where $n$ is number of points on a convex hull? I have just done it in linear time where I checked for upper ...
- 235
1
vote
1
answer
388
views
Clarification for binary search in solving optimal TSP when a polynomial algorithm with a budge exists
Below is Question 8.1 in Algorithms by Dasgupta et al.
There's a solution to this problem that uses binary search from here. Pasting the answer for posterity.
My questions are:
When they say input ...
- 649
0
votes
2
answers
161
views
How to determine the max offset of a value, given the range, step size and amount of steps
Given
The starting and the end values of X
The maximum step (maximum delta)
Exact amount of steps
I need to determinte the maximum and the minimum possible values that X could become during this ...
- 31
0
votes
1
answer
207
views
If possible, use binary search to find an element in sorted array
Given sorted array $A[1..n]$, we want to find an element such that,
$A[i]=i^2$,Can we use binary search to find such a element?
My Attempt:
initially, I read this link, but I can't understand the ...
user132812
1
vote
1
answer
97
views
Time complexity of binary search
Proposition: The binary search algorithm runs in $O(\log n)$ time for a sorted
sequence with $n$ elements.
When justifying this claim, first we say that with each recursive call the number of ...
- 135
0
votes
1
answer
144
views
Find Index In Sorted Array Such That A[i] = C1 * i + C2
I'm already know that there is an algorithm that can solve A[i]=i in O(log(n)) in a sorted array.
But I want to know if there is any kind of algorithm that also can solve A[i] = C1 * i + C2 (witch C1 ...
- 103
1
vote
0
answers
86
views
Splay tree amortized analysis cost using Access Lemma
Currently studying for an algorithms exam and I came across this question and solution, but I can't understand the solution where it references nodes of depth less than $4\log n$ and not restructuring....
- 11
1
vote
2
answers
325
views
Theoretical lower bound of finding number of occurrences of a target integer in a sorted array
Given a sorted array of integers and a target integer, find the number of occurrences of the target integer.
It is well-known that a binary search has time complexity $O(\lg n) $ where $n$ is the ...
- 169
0
votes
0
answers
52
views
Does this problem have a formal name?
I have come across the following problem but am unable to understand the solution for it. Hence I would like to know if it has a formal name then, I can search for it and read about it in more detail. ...
- 215