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
2
votes
1answer
46 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
46 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 ...
2
votes
1answer
43 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 ...
0
votes
0answers
12 views

What is the work complexity for optimal merge using partitioning of sorted array of size n and p processors with segments of size n/p?

Using optimal method to find rank, we can partition a sorted array(size n) in segments of size n/p using p processors. The, we can find the rank of an element by placing a processor at the start and ...
1
vote
0answers
22 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
2answers
50 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
100 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
27 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 ...
0
votes
0answers
34 views

time complexity of 2 sum problem using binary search

this is a popular searching problem and the question is : Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The ...
2
votes
1answer
30 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
35 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
29 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. ...
1
vote
1answer
39 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 that indexed from 0 to N-1 and I have to find K of them that answer some condition. The naive ...
0
votes
0answers
21 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
77 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
65 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
22 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
77 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
118 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
52 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
78 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
82 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
261 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
429 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
157 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
73 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
803 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
61 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
30 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
303 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
632 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
128 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
102 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
190 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
20 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
57 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
5k 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
80 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
405 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
1k 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
1k 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
95 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
509 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
560 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
152 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, ...
35
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
211 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:...