The tag has no usage guidance.

learn more… | top users | synonyms

13
votes
2answers
251 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 ...
11
votes
2answers
2k 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
564 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
52 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
37 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
37 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
201 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
203 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
28 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 ...
-1
votes
5answers
301 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
22 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
52 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
82 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
70 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
102 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
35 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
246 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 ...
3
votes
1answer
817 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
526 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
60 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
18 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
7k 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
626 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 the ...
37
votes
3answers
11k 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', we'...
3
votes
3answers
125 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
249 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
93 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
225 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 ...
1
vote
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
165 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
87 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 ...