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
0answers
17 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 ...
2
votes
2answers
63 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
61 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
21 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
45 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
108 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
31 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
48 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
76 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
156 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 ...
2
votes
3answers
419 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
107 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
46 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 ...
3
votes
1answer
698 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
54 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
29 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
261 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
460 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 ...
1
vote
0answers
125 views

Feeding real-time data and binary search algorithm termination

This question was asked in our exam long a go and I don't remember exact words. The scenario was, Initially you are given a set of finite data to start with, and a key value (which you have to find ...
0
votes
0answers
87 views

Problem in understanding approach of binary search w.r.to question

Monk and his best friend Micro were taking a stroll, when they found an array A having N integers lying on the road. The array was injured badly, so they took it with them and treated it. When the ...
3
votes
2answers
171 views

Invariant on “Find K Closest Elements” problem

I run across this problem: Given a sorted array, two integers k and x, find the k closest ...
0
votes
0answers
17 views

calculate the complexity of binary search algorithm [duplicate]

How do i calculate the complexity of this algorithm at the best case and its complexity at the worst case and the average complexity by assuming that the probability that the element is in the list is ...
-1
votes
1answer
19 views

Find longest interval if the intervals can propagate from one to another

Let's say we have given $n$ points on the x-axis, each point described with two integers: $x_i, a_i$, $x_i$ meaning it's position on the x-axis, and $a_i$ meaning that it can activate all the points ...
0
votes
0answers
27 views

Unusual function - operations on lists / sets - possible optimization

I have a problem. Below I present a function in Python. ...
1
vote
0answers
49 views

How to assign the increasing keys to the nodes of a complete binary tree on n nodes in inorder?

I'm looking at the Multiplicative Binary Search and come across this. It's the preparation you need to do for you to use the Multiplicative binary search procedure. I somehow do not know how to do ...
0
votes
2answers
3k views

Number of comparisons in Binary search

I know this question is very trivial to ask, but I have got some doubt while solving this problem.Code is given below ...
1
vote
1answer
66 views

Are divide and conquer searches applicable to unimodal decision problems?

Given a sorted list of booleans with consecutive 0s followed by consecutive 1s such as [0,0,0,0,1,1,1], binary search is able to find the first 1 after all the 0s in log(n) time. Is this technique ...
1
vote
1answer
329 views

Best Algorithm for searching for an index in an array such that A[i] = i

Recently i got a question in one of my exams about asking for an algorithm which searches an element in a sorted array such that $A[i] = i$. My algorithm was based on binary search and did a $O (\log ...
0
votes
1answer
877 views

How do I find maximum and minimum number of times the search loop will execute when searching through an array of 1,048,576 integers

I have tried to calculate the maximum number of times the loop will search through this large array, but I am not sure if I have that correct and I also need help with or pointers of how I can ...
4
votes
2answers
927 views

Why is binary search using this weird thing to calculate middle?

I noticed that in many books calculation of midpoint for binary search uses this: int mid = left + (right - left) / 2; Why not use ...
1
vote
4answers
86 views

Locate all locations in a sorted array where arr[i]<arr[i+1]

Suppose you are given an array of $n$ integers with duplicates in non-decreasing order. The goal is to find the locations where a value is different from its neighbor. For example, given the array $...
1
vote
2answers
447 views

Computational complexity comparison of floating-point Euclidean distance calculation with binary fixed-point Hamming-distance calculation

This could relate to different applications, but my application of interest is in similarity-search systems based on high-dimensional feature vectors. In these systems, since search based on ...
2
votes
1answer
493 views

The use of binary search when determining whether a point lies inside a given convex hull

In an answer to the problem of determining whether or not a point lies inside a given convex hull, a thesis is mentioned, which says : For repeated queries with preprocessing allowed, we develop a ...
1
vote
2answers
143 views

Optimal generalized bisection method

Suppose I'm looking for a some unknown number $x$ in the interval $[a,b]$ under the following assumptions: $x$ is unique. Given any $t \in [a,b]$ I can check, at some fixed computational cost, ...
33
votes
2answers
10k views

Why is the log in the big-O of binary search not base 2?

I am new to understanding computer science algorithms. I understand the process of the binary search, but I am having a slight misunderstanding with its efficiency. In a size of $s = 2^n$ elements, ...
0
votes
0answers
27 views

Hash function for searching, is that feasible?

I have a set of sorted values $\left\{a_j \right\}_{1 \leq j \leq n}$, suppose now a number $x$ is given and we would like to find out the index $j$ such that $a_j \leq x < a_{j+1}$ (you can assume ...
4
votes
1answer
205 views

Fastest search algorithm in a sorted list with certain error rate-limiting constraints

This problem came up during the Google CTF 2017. For background information about the challenge you can search for GoogleCTF A7 ~ Gee cue elle. Problem description:...
2
votes
2answers
2k views

How exactly Hashing performs better than a Binary Search?

The time complexity of a Binary Search is O(log n) and Hashing is O(1) - so I've read. I have also read that Hashing outperforms Binary search when input is large, for example in millions. But I see ...
2
votes
1answer
376 views

Searching a sorted array to find the $k$ closest values to a target value $T$

Let $A$ be a sorted array of $N$ values. I am interested in finding the index $j$ such that the elements $A_j, A_{j + 1}, ..., A_{j + k - 1}$ have the $k$ closest values to the given target value $T$. ...
2
votes
1answer
72 views

Efficient search algorithm for a monotonic boolean array wherein the probability of target's location is available apriori

A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$. $$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in ...
1
vote
1answer
61 views

Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function

A boolean-valued function defined in the set of positive integers, $\mathcal Z$. $$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in \mathcal Z $$...
0
votes
1answer
254 views

Algorithm for finding the minimum index in array with value exceeding x

Given a set $S = \{s_1, \ldots, s_k\}$, find the minimum index $j$ such that $\sum_{i = 1}^j s_i \geq \frac{1}{2}\sum_{i = 1}^k s_i$. I was reading in a paper about an algorithm for this problem that ...
4
votes
1answer
196 views

lower bound for Renyi–Ulam Game with lies

Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ). Game : $A$ chooses an element in {1,2....,n} $B$ tries to ...
0
votes
0answers
89 views

Search in a sorted array (Binary search)

My lecture states that search in a sorted array can be done in ω(n). Why is that? I know it can be done with "normal" search in Θ(n) and with binary search in O(log(n)). My guess would be, make the ...
2
votes
1answer
98 views

Approximation with imperfect dichotomy oracle

Given an unknown $x$ and an oracle $O(r)$ such that: If $O(r)$ is true then $x \geq r$. If $O(r)$ is false then $x < 2r$. Conversely, the oracle has a defined behaviour only outside the interval $...
1
vote
2answers
8k views

Binary search algorithm - worst-case complexity

I tried to calculate the worst case of binary search (not binary search tree). My calculations: $$T(n) = T(\frac{n}{2}) + 1$$ $$T(n) = T\left(\frac{n}{4}\right) + (1+1) = T\left(\frac{n}{8}\right) + (...
6
votes
2answers
3k views

Why is the time complexity of insertion sort not brought down even if we use binary sort for the comparisons?

There are two factors that decide the running time of the insertion sort algorithm : the number of comparisons, and the number of movements. In the case of number of comparisons, the sorted part (left ...
5
votes
4answers
351 views

Finding a value in a sorted array in log R time, R is the number of distinct elements

The standard binary search algorithm gives log N time, where N is the total number of elements in the array. When the array has duplicates, I don't see how you could detect those duplicates ahead of ...
14
votes
2answers
541 views

Is there any study or theory behind combining binary search and interpolation search?

I just read Can this algorithm still be considered a Binary Search algorithm? and recalled that a few years back I wrote an indexer/search for log files to find log entries in large plain text files ...
12
votes
3answers
3k views

Can this algorithm still be considered a Binary Search algorithm?

While doing the second code kata (which asks you to implement a binary search algorithm five times, each time with a different method), I've come up with a slightly different solution which works as ...