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.
134
questions
-1
votes
1
answer
36
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 ...
- 3
0
votes
1
answer
64
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
0
votes
1
answer
78
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]
...
1
vote
0
answers
54
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', ...
2
votes
2
answers
628
views
How can I apply binary search to find two adjacent increasing elements in an unsorted array?
I need to write a function that gets an array of numbers $a$ as an input and returns an index $i$ such that $a[i]<a[i+1]$ if it exists, if such $i$ doesn't exist return $-1$. (return any index $i$ ...
- 164
3
votes
1
answer
27
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
2
answers
109
views
O(Log n) Search - Array
So, there's a LeetCode problem that has you find a O(log n) solution to finding a target number in a rotated sorted array.
As an example:
...
0
votes
0
answers
67
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, ...
- 481
1
vote
2
answers
418
views
How to use the step count method correctly for binary search?
I've tried to use the step counting method to get the worst-case time complexity for binary search. But I seem to mess it up, as my final result would be O(n) and ...
- 13
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
0
votes
3
answers
119
views
Fastest Algorithm for "Merge" step in Mergesort
Given two sorted arrays $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_m$, merge them together into one sorted array $c_1,c_2,\dots,c_{n+m}$ containing the elements of $a$ and $b$.
The typical mergesort ...
- 11
1
vote
0
answers
1k
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 ...
- 150
2
votes
1
answer
544
views
Binary Search return value
Google has the article Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Which primarily discusses the overflow on the mid calculation. However, what I found ...
- 145
0
votes
1
answer
169
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 &...
1
vote
1
answer
75
views
Algorithm to find approximate position of element from a noisy sorted list
Let's have a static function f(n) which for a given n returns only these answers "lower" or "higher" comparing against an imaginary number x
In a sorted list ...
- 111
0
votes
1
answer
92
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
0
votes
1
answer
48
views
Search algorithm for an expensive boolean function
I have the following problem. We have a boolean function $f$ that is expensive to compute for a given input. We need to find the smallest positive integer $n$ such that $f(n)$ is true. We don't know ...
-1
votes
1
answer
97
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 ...
- 23
1
vote
1
answer
205
views
How to do binary search on a path in a binary heap
I am trying to solve this question:
Let's say you have a binary heap and an index $i$, design an algorithm that finds if a number $x$ appears in the path between the root of the heap and $heap[i]$ in ...
- 49
2
votes
1
answer
76
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
2
votes
1
answer
151
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 ...
- 33
1
vote
1
answer
1k
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
50
views
How can I make my algorithm more efficient?
I came across an algorithmic problem. I do not know how to do it optimally.
The problem is as follows:
There is an increasing array $A$ of size $n_1$
There is an array $M$ of queries of size $n_2$
...
- 13
1
vote
1
answer
150
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 ...
- 659
0
votes
1
answer
264
views
How to split the array into two subarrays with the smallest sum difference?
Given
An array of elements, all elements are positive (unsorted, but sorting is not a problem if required)
The objective:
To create two subarrays, so that ...
- 33
1
vote
1
answer
60
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 ...
- 33
2
votes
1
answer
101
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 ...
- 33
0
votes
1
answer
137
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
2
votes
1
answer
261
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)$. ...
1
vote
1
answer
38
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
4
votes
1
answer
244
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: ...
- 113
0
votes
1
answer
85
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
2
votes
1
answer
49
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 ...
- 123
1
vote
0
answers
49
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
6
votes
1
answer
153
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 ...
- 163
1
vote
2
answers
220
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
11
votes
6
answers
2k
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.
...
- 119
0
votes
0
answers
33
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
0
votes
1
answer
847
views
can we do binary search to solve quadratic equation?
Suppose i have a quadratic equation like this, 2x^2 - 4x - 5 = 0, the solution here is x1=2.87 and x2=-0.87. I tried this python snippet to find the non-negative ...
- 15
0
votes
1
answer
554
views
Is there a faster than O(n^2) solution for Box stacking problem?
The Box Stacking problem is as follows:
You are given a set of $n$ types of rectangular 3-D boxes, where the
$i^{th}$ box has height $h_i$, width $w_i$ and depth $d_i$ (all real
numbers). You ...
- 17
-1
votes
1
answer
2k
views
binary search terminating condition (left != right) vs (left <= right)
I have seen several implementations of binary search where they can use either (left != right) or (left <= right). For example, in normal binary search where you check if target value is in the ...
- 121
1
vote
1
answer
178
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 ...
- 29
0
votes
0
answers
479
views
Job Scheduling with deadline with $nlogn$ algorithm
We know that there is a Greedy algorithm for scheduling of $n$ jobs which each job has its own deadline and profit.
In greedy algorithm, we sort the set by their profit descendant, And if a job can ...
- 1
2
votes
1
answer
490
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
<...
- 123
0
votes
0
answers
131
views
Is there an O(n) solution for this problem?
I have found this problem on CodeForces.The problem is in the following link: https://codeforces.com/problemset/problem/729/C
Problem Starts here:
Vasya is currently at a car rental service, and he ...
user102382
1
vote
1
answer
348
views
Find $n'th$ perfect number , where perfect number is a positive integer whose sum of digits is $10$
For example $46$ is a perfect number , since $4+6=10$ . If $n=1$ , answer is $19$. If $n=2$ , answer is $28$. If $n=3$ , answer is $37$ and so on .We need to make a program which takes $n$ and ...
user109308
1
vote
0
answers
28
views
Intersection of 2 arrays
Here is a question i came across :
Given two arrays, write a function to compute their intersection.Here we will allow the duplicates.
Note:
Each element in the result should appear as many ...
- 159
1
vote
3
answers
161
views
Dividing 2 integers with some constraints
This a problem i came across while practicing binary search. Here is the problem:
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
...
- 159
2
votes
2
answers
281
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-...
- 163
2
votes
0
answers
555
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 ...
- 121