The binary-search tag has no usage guidance.
-1
votes
0answers
18 views
worst case time complexity [on hold]
For binary search i am able to calculate the average case complexity but i don't know how to find worst case complexity?Please help
3
votes
1answer
32 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
57 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 ...
0
votes
0answers
37 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 ...
0
votes
1answer
34 views
Order a list of edges to make the the complexity of searching for an edge O(lg E)
I was reading this article on how to represent graphs, and probably the simplest way to think about it is to have a list of edges, with an edget being usually a list of the vertices that are related ...
2
votes
0answers
28 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 ...
6
votes
1answer
197 views
Optimize binary search on Segment Tree by storing past result
Goal
Let $A[n]$ be an arbitrary array of integers of length $n$. Let $S$ be a segment tree, represented by an array of records: each record containing the left and right bounds ($[l,r]$) of the ...
2
votes
1answer
208 views
Potential method for dynamic binary search
I'm trying to solve 17-2(b) problem from Cormen(CLRS) using potential method.
Problem from Cormen:
17-2 Making binary search dynamic
Binary search of a sorted array takes logarithmic search time, ...
3
votes
2answers
218 views
first intersection of two arrays of integers - double binary search feasible?
I'm interested to find the fastest possible way to find the first element of an intersection of two integers arrays (first match)
Looking for the 'fastest' algorithm I have seen different methods ...
1
vote
1answer
49 views
Finding Triples that satisfy modulo equation in $O(n\log n)$ time
Given $n$, I am trying to count the number of values $(a,b,c)$ that satisfy the following equation in $O(n\log n)$ time. I do not need the values themselves only the number of total values that ...
1
vote
2answers
17 views
Order of storage of pointers for a linked list of length n
I have a linked list in which I have kept the elements in order (increasing/decreasing). I want to be able to perform a binary search on this linked list. For this I am keeping pointers to the middle ...
0
votes
1answer
3k views
Proving that the average case complexity of binary search is O(log n)
I know that the both the average and worst case complexity of binary search is O(log n) and I know how to prove the worst case complexity is O(log n) using recurrence relations.
But how would I go ...
5
votes
2answers
294 views
Compute square root using (bit) additions and shifts as primitives
Question: Given an $n$-bit natural number $N$, how to compute $\lceil \sqrt{N} \rceil$ using only $O(n)$ (bit) additions and shifts?
The tip is to use binary search. However, I could not achieve ...
32
votes
4answers
8k views
Why is binary search faster than ternary search?
Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space.
If, instead, we used 'ternary search', ...
3
votes
3answers
107 views
Minimum number of tests to identify subset of modules that trigger a bug?
I have an ordered set of $M$ software modules compiled together. The interaction of some $N$-tuple of these modules is causing a bug when the program is run.
I can run the program with any desired ...
1
vote
2answers
160 views
Searching for a string of numbers in a large digit sequence [closed]
How would one search for a string of digits in a large digit sequence? For example, I'd like to search for 351814 in Euler's number. I'm not too keen on computer ...
0
votes
0answers
20 views
Uniform Binary Search explanation and lookup table [duplicate]
Please can anyone explain me the worst ,average and best case running time for the Unifrom binary search .. Also how can the lookup table be explained?
1
vote
0answers
87 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 ...
-1
votes
2answers
112 views
BST Successor Proof
I'm studying for my CS final and I can't seem to get the anywhere with one of the questions.
This is the question:
Prove that if a node in a BST has a successor, but has no right child, then its ...
0
votes
1answer
2k views
How to analyze/test a binary search algorithm?
I was asked to "Compute the average runtime for a binary search, ordered array, and the key is in the array." I'm not quite sure how to approach this problem. Isn't the runtime of binary search O(log ...
4
votes
1answer
158 views
Searching a value in a “piecewise” ordered array
If we have an array $A$ of length $N$, which is partitioned into $\sqrt{N}$ adjacent subarrays $A(i)$, each of which is monotonically ordered from $\min(i)$ to $\max(i)$ (it is known what places have ...
2
votes
1answer
68 views
Finding a '1' cell with a '0' to its right in a binary array
Given an array of size n that holds ones and zeros I need to find an index of a 1 cell that has 0 to his right (in then next ...
