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.

23 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
423 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
0answers
56 views

Two flavors of red-black trees with different performance

I've implemented two red-black trees (using the pseudo-code in CLRS) with slightly different flavors: 1) In the first tree, all the data is stored in the leaves. 2) In the second tree, the data is ...
1
vote
1answer
32 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 ...
1
vote
0answers
27 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....
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
0answers
129 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 ...
1
vote
0answers
68 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 ...
1
vote
0answers
198 views

Binary search transition point of a function on stream

Consider an unknown function $f(x,y)$, where $x$ and $y$ are just two scalar numbers in $[0,1]$. $f(x,y)$ is an increasing function of $y$ and is between $0$ and $1$ but is unknown. At each time I ...
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
0answers
317 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 ...
0
votes
0answers
111 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 ...
0
votes
0answers
418 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 ...
0
votes
0answers
55 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 ...
0
votes
0answers
82 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\...
0
votes
0answers
136 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{...
0
votes
0answers
285 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 ...
0
votes
0answers
120 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 ...
0
votes
0answers
269 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 ...
0
votes
0answers
29 views

Unusual function - operations on lists / sets - possible optimization

I have a problem. Below I present a function in Python. ...
0
votes
0answers
28 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 ...
0
votes
0answers
108 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 ...
0
votes
0answers
63 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 ...
0
votes
0answers
715 views

Find the index of minimum number that is greater than key given of a sorted array, does these two functions return same result?

Give an array of integer has been sorted (non-decreasing order), we need find the index of minimum number number that is greater than key given, I wrote two functions, they're identical except the ...