Skip to main content

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
0 votes
0 answers
22 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, ...
Electro's user avatar
  • 103
-1 votes
0 answers
19 views

Using Binary Search to Calculate the nearest 2d Co-ordinate from a list , Leetcode#2812

I am solving this question Problem Link through a different method , the only difference between the the official solution and my approach is that, The official Solution uses BFS(Multisource) to ...
Shubham Kumar's user avatar
1 vote
2 answers
28 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 ...
jam's user avatar
  • 13
0 votes
0 answers
16 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 ...
Christian Webb's user avatar
1 vote
1 answer
133 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 $...
Erel Segal-Halevi's user avatar
2 votes
1 answer
51 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 ...
user716881's user avatar
1 vote
1 answer
54 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 ...
Hugh Mann's user avatar
0 votes
0 answers
40 views

How to optimally construct queries asking about the class of an object to eventually find it?

Consider the following problem stated formally: You are given $n$ objects $o_1$, $o_2$, ..., $o_n$ and $k$ classes $c_1$, $c_2$, ..., $c_k$, each class containing some objects; an object is chosen. ...
sbh's user avatar
  • 51
1 vote
1 answer
142 views

Median of two sorted arrays

Two sorted arrays A and B are given having size l and m ...
Shashikant's user avatar
5 votes
1 answer
101 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 ...
Albert Hendriks's user avatar
3 votes
1 answer
48 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 ...
Jack Sack's user avatar
0 votes
0 answers
32 views

Finding minimum in a descending rotated sorted array with duplicates

For this question (154. Find Minimum in Rotated Sorted Array II ), I have a solution: ...
Dracula's user avatar
  • 103
0 votes
1 answer
64 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}$ ...
EvaMGG's user avatar
  • 167
2 votes
1 answer
82 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 ...
Erel Segal-Halevi's user avatar
-1 votes
1 answer
64 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 ...
Mocak's user avatar
  • 15
0 votes
1 answer
243 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 ...
J Wang's user avatar
  • 11
1 vote
3 answers
121 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] ...
Minh Đức Hoàng's user avatar
1 vote
0 answers
76 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', ...
Surprised Seagull's user avatar
2 votes
2 answers
988 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$ ...
Pwaol's user avatar
  • 164
3 votes
1 answer
50 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'...
user150391's user avatar
0 votes
2 answers
259 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: ...
Campbell Hutcheson's user avatar
0 votes
0 answers
73 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, ...
Avv's user avatar
  • 505
1 vote
2 answers
831 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 ...
Flajt's user avatar
  • 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 ...
coolest 10's user avatar
0 votes
3 answers
177 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 ...
usc18's user avatar
  • 11
1 vote
0 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 ...
Ashkan Khademian's user avatar
2 votes
1 answer
1k 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 ...
worbel's user avatar
  • 145
0 votes
1 answer
248 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 &...
Soumya Patel's user avatar
1 vote
1 answer
150 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 ...
nehem's user avatar
  • 111
0 votes
1 answer
141 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 <...
student010101's user avatar
0 votes
1 answer
60 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 ...
Dmitry Kamenetsky's user avatar
-1 votes
1 answer
112 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 ...
Glubs's user avatar
  • 23
1 vote
1 answer
338 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 ...
yuval's user avatar
  • 49
2 votes
1 answer
94 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. ...
Gilboot's user avatar
  • 147
2 votes
1 answer
168 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 ...
Filipe Costa's user avatar
1 vote
1 answer
2k 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 ...
Exzone's user avatar
  • 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$ ...
southpaw's user avatar
1 vote
1 answer
310 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 ...
heretoinfinity's user avatar
0 votes
1 answer
513 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 ...
Mykhailo's user avatar
0 votes
2 answers
80 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 ...
Mykhailo's user avatar
2 votes
1 answer
167 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 ...
Mykhailo's user avatar
0 votes
1 answer
151 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 ...
user avatar
2 votes
1 answer
441 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)$. ...
ABHIJEET SHUKLA's user avatar
1 vote
1 answer
53 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 ...
GilbertS's user avatar
  • 135
4 votes
1 answer
274 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: ...
Elliott's user avatar
  • 113
0 votes
1 answer
98 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 ...
Mahdi Zakizadeh's user avatar
2 votes
1 answer
51 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 ...
huzzm's user avatar
  • 123
1 vote
0 answers
64 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....
D Wot's user avatar
  • 11
6 votes
1 answer
189 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 ...
Craig's user avatar
  • 163
1 vote
2 answers
284 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 ...
Idonknow's user avatar
  • 169