Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [binary-search]

The tag has no usage guidance.

0
votes
0answers
18 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
428 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 ...
0
votes
0answers
30 views

When to use which variant of the loop condition in binary search?

When solving a search problem with binary search, sometimes the loop condition is while low < hi and sometimes it is ...
1
vote
1answer
36 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
25 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
126 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
52 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
115 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
47 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
1answer
95 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
16 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
35 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
2k 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
50 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
158 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
557 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
293 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
76 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
264 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
373 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
113 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, ...
32
votes
2answers
9k 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
179 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
736 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
336 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$. ...
3
votes
1answer
62 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
52 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
136 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 ...
5
votes
1answer
164 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
83 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
97 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 $...
0
votes
2answers
5k 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) + (...
5
votes
2answers
2k 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
275 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
492 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 ...
4
votes
3answers
960 views

Categorization of Binary search as Divide and Conquer

Why do we call binary search as 'Divide' and 'Conquer' strategy? It does not combine the results unlike other Divide and Conquer strategies.
1
vote
1answer
790 views

Prove that the depth function of a Binary Search Tree is $O(\log n)$ on average

I am struggling with this question because I am not sure how to see that a depth function is $\mathcal{O}(\log n)$ on average when it clearly traverses through the whole tree which should make it $\...
0
votes
1answer
127 views

Total number of calls during insertion into binary tree

The problem: Find a formula for the total number of calls occurring during the insertion of n elements into an initially empty set. Assume that the insertion process fills up the binary search tree ...
1
vote
0answers
182 views

retrieve file format from unknown binary file [closed]

Is it possible, somehow, maybe by using some kind of brute force algorithm, to try and figure out what kind of file one is dealing with when one only has the raw binary without file format or meta ...
2
votes
1answer
926 views

Finding median of three sorted array (the same length)

I think about following problem: There are given three sorted arrays $A,B,C$ (each of them is length $n$). Every array has distinct elements. Find median of union $A,B,C$. I consider following ...
1
vote
1answer
553 views

I know Binary Search is more efficient than Ternary search, but my results are opposite. Help interpreting results?

I have a piece of code that applies recursive Binary and Ternary searches on sorted arrays of increasing size, i.e. 500, 1000, 2000, 4000, etc. The entire code segment is about 200 lines so I've been ...
0
votes
0answers
53 views

Fast Raytracing Algorithm or Alternative needed

I have a grid that shows the world and its coastlines. An excerpt from the area around the UK is shown here From an arbitrary origin point anywhere in the ocean, I want to find those coastline points ...
-1
votes
5answers
762 views

How can there be 10 steps in the binary search algorithm for the phone book search problem?

The following example was given in an online lecture I was watching. A phone directory is 1000 pages long, and we have to find the name "Zurich Smith". The algorithm is as follows: Split the phone ...
1
vote
0answers
93 views

Fractional cascading vs merge [closed]

Fractional cascading allows me to search in k ordered lists. It requires every list to have same ordering (how would I otherwise insert elements from the cascade below, preserving order?). But why is ...
3
votes
1answer
69 views

Finding the number of $L\leq j\leq R$ such that $a[j] \leq a[i]$

I have recently encountered the following problem which I heard can be solved by using BIT (binary indexed trees) but I am not sure how: Given an array $a[1, 2, \ldots, n]$ and $Q$ queries of the ...
-1
votes
1answer
304 views

augmenting AVL, intervals

Show how to augment dictionary of intervals (insert, delete, search) in order to make possible answer to following questions: Check if given interval $[a, b]$ intersects with some interval in a ...