The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
2answers
57 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 ...
3
votes
0answers
57 views

Finding a median in a union of sets given as sorted arrays [migrated]

You are given $k$ sorted arrays $A_1, A_2, ..., A_k$, each containing $n$ elements. How fast can you compute the median of $A_1 \cup A_2 \cup ... \cup A_k$ ? I have a solution running in ...
1
vote
1answer
43 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
16 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
115 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
145 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 ...
29
votes
3answers
6k 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', ...
0
votes
0answers
12 views

How to calculate the complexity of Uniform Binary Search algorithm [duplicate]

I was studying the Uniform Binary Search algorithm authored by Donald Knuth which is an optimization of the classic Binary Search algorithm. Can someone explain the complexity analysis for Uniform ...
3
votes
3answers
90 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
119 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
70 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
88 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
1k 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
156 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
66 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 ...