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
1
vote
1answer
35 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 ...
1
vote
1answer
47 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$ ...
0
votes
1answer
15 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 ...
0
votes
1answer
15 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 ...
1
vote
1answer
27 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 ...
2
votes
1answer
57 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 ...
0
votes
1answer
28 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 ...
2
votes
1answer
44 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
1answer
28 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 ...
0
votes
1answer
53 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 ...
2
votes
1answer
43 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 ...
1
vote
0answers
23 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....
6
votes
1answer
145 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 ...
1
vote
2answers
57 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 ...
11
votes
6answers
1k 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. ...
0
votes
0answers
32 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. ...
0
votes
1answer
203 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 ...
0
votes
1answer
169 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 ...
-1
votes
1answer
390 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 ...
2
votes
1answer
121 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 ...
0
votes
0answers
211 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 ...
2
votes
1answer
252 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 <...
0
votes
0answers
96 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 ...
1
vote
1answer
188 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 ...
1
vote
0answers
26 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 ...
1
vote
3answers
87 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. ...
2
votes
2answers
119 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-...
1
vote
0answers
308 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 ...
2
votes
1answer
463 views

number of comparisons in searching algorithms

i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these. For linear search : ...
0
votes
0answers
315 views

Finding the rightmost element in an array of duplicate elements using binary search

i was reading Binary Search in the wikipedia and i came across this part of 'rightmost index of an element in an array of duplicate elements'. i understood the process of determining the leftmost ...
2
votes
1answer
34 views

Smallest segment after whose removal all elements are distinct

I am interested in the following problem: We are given an array of integers and we need to find the size of smallest subsegment such that after removing it all elements in the array are distinct. ...
2
votes
1answer
52 views

Extend binary search

There is a way for finding K entries of N given entries using a binary search? I mean, I have N entries, indexed from 0 to $N-1$ and I have to find $K$ of them that satisfy some constraint. The ...
0
votes
0answers
44 views

Linearithmic solution to finding closest pairs in an array of N elements

I am reading Algorithms 4ed by Sedgewick and Wayne. I came across this algorithm design question that asks the following: Write a program that given an array of N integers, finds a closest pair: two ...
3
votes
2answers
274 views

Binary search uneven split number of queries?

For even split binary search (repeated halving) number of queries is log with base 2. According to Skiena's Algorithm Design Manual, if the split in binary search is by ratio 1/3:2/3 instead of 1/2:1/...
3
votes
1answer
70 views

Finding $k$-th element in prefix of size $i$

Let's say we are given array $A$ of size $n$. We need to answer some numbers of queries. For each query we are given index $i$ and integer value $k$, $k \le i$. If we take the first $i$ elements of ...
0
votes
0answers
53 views

Exponential search worst-case performance

I'm learning about Exponential search and I keep reading that the worst-case performance is $\log_2 i$ where $i$ is the searched index. I tried with an array containing $1073741824$ elements ($1024\...
2
votes
1answer
522 views

In which situation do we choose randomized binary search instead of the normal binary search?

Both randomized and normal binary search takes O(log n) time complexity but why does the randomized version exist? In other words what is the advantage of randomized binary search even if it has same ...
0
votes
1answer
151 views

How can I understand a hint for finding the lowest height of the last bulb in a Garland?

Disclaimer This is not from an ongoing contest, this is from my course on edx of ITMO. Also this is a paid courses so the direct link to the problem is not useful unless you also register this course....
0
votes
0answers
117 views

Minimum Ratio Spanning Tree

Problem statement: Given an undirected graph $G = (V, E)$ with edge $e_i$ having two associated positive values $c_1, c_2$. Find a spanning tree $ST$ such that (ratio of the spanning tree): $$\frac{...
1
vote
1answer
350 views

Finding an interval in a binary search tree that contains a point

I have a binary search tree where nodes are non-overlapping intervals. I'm given a point, and I need to determine which interval the point belongs to (if any). This is easy to do because I can compare ...
0
votes
0answers
240 views

Binary search on a path of minimum heap

WhereTo(H,X) is searching for the place to set X (an integer) in a minimum heap-H. The function is executing a binary search on a path of a heap. Assumption: We have the specific path because it ...
1
vote
1answer
688 views

An algorithm that find the max X/Y in a polygon in O(log n)

I got a task to create two functions one finds max $X$ and the other $Y$ in a polygon in $O(\log n)$. The polygon is represented by an array of its vertices where each vertex is represented by its ...
3
votes
3answers
545 views

Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))

Given a sorted array $A[1,\ldots,n]$ and element $x$ that located at position $k$. We know $x$, we don't know $k$. Write an algorithm that finds $k$, in $O(\min(\log k, \log(n-k))$ time complexity. ...
0
votes
1answer
374 views

Binary search in log time on a Turing Machine

I was thinking about TM (Turing Machine) as a computation model, and I came up with the following question : Is it possible to make a TM that answers binary search (tell wether $x$ belong to a sorted ...
0
votes
0answers
110 views

Worst case lower bound of binary search

For the question below, it is asking to prove the lower bound on the worst case is log(n). I have no problem proving this and the solution makes 100% sense to me. However, there is a comment at the ...
4
votes
1answer
2k views

How binary search works in real world scenario?

In binary search, we need an array of integers for it to search for an element. Also, many other sorting algorithm sorts array of integers. But in real world, we may search for a name of an employee ...
1
vote
1answer
114 views

Searching in a Binary Search Tree

I'm studying Binary Search Trees (BST) and I would like to verify that my understanding of BSTs is correct. For example, let S = [17, -10, 7, 19, 21, 23, -13, 31, 59]. Binary Search Tree for S, with ...
1
vote
1answer
34 views

Peaking finding when equals is taken out of the equation

I am going through the online course MIT OCW 6.006, lecture 1. It introduces a binary search algorithm that finds a peak in O(lgN) time. A peak A[i] is defined as ...
3
votes
2answers
354 views

Binary search with alternative comparison cost

I have a sorted array $A$ of non-arbitrary elements. Now, I have another element $c$ and I want to find out where it belongs in the sorting of $A$. The cost of comparing $c$ to $A_i$ is $\Theta(i^2)$. ...
1
vote
1answer
1k views

Understanding Binary Search for Kth Smallest element in an Array

The Answer here shows a way to solve the problem with O(1) space. The approach uses Binary Search. I am finding really hard to wrap my head around why it works. I get why we did low + (high-low)/2 ...