0

I was trying to solve this : Given a sorted array that contains continuous integers starting from 0(one integer may be repeated many times) eg - 0,0,0,1,2,3,3,3,4,4(can be very long also - this is just an example) , efficiently find the starting and ending indices of a given integer.

I am thinking of using

1)traversal(complexity = O(n))

2) a modified binary search(complexity =O(log n)). [ n = length of total array]

Then was wondering if the continuous integers property could be utilized to solve it. Any different ideas or suggestions ?

Improve this question
8
  • Binary search would be useful only, if the sequence length is much larger than the max number. Commented Jul 6, 2012 at 17:40
  • Agreed that if the sequence length is very small , binary search wouldnt be of much use , any other ideas ? Commented Jul 6, 2012 at 17:43
  • i would hop in sets of 3 as you can peek ahead 1 and back one... That way you can stop if you are OOB, and would low you to jump at a faster rate... (1/3 the iterations.) granted, looking ahead and behind cost some cost, but not as much as iterating the loop as many times as you are. Commented Jul 6, 2012 at 17:44
  • @Fallenreaper: OOB ? Granted this would reduce the number of iterations of method 1 but it would be slower than the binary search method... Commented Jul 6, 2012 at 17:47
  • 1
    Really, the fastest way to do this would be to mark down these indexes while you were sorting the array! Commented Jul 6, 2012 at 18:11

4 Answers 4

Reset to default
1

To begin, let's ignore the "continuity" property

As long as the problem is about finding the most efficient way to handle a single individual request, the straightforward general solution would be to perform two consecutive binary searches: the first one finds the beginning of the sequence, the second one finds the end of the sequence. The second search is performed in the remainder of the array, i.e. to the right of the previously found beginning of the sequence.

However, if you somehow know that the average length of the sequence is relatively small, then it begins to make sense to replace the second binary search with a linear search. (This is the same principle that works when merging two sorted sequences of similar length: linear search outperforms binary search, because the structure of the input guarantees that on average the target of the search is located close to the beginning of the sequence).

More formally, if the length of the whole array is n and the number of different integer values in the array (variety metric) is k, then linear search begins to outperform binary search on average when n/k becomes smaller than log2(n) (some implementation-dependent constant factors might be needed to come up with a practical relationship).

The extreme example that illustrates this effect is the situation when n=k, i.e. when all values in the array are different. Obviously, using the linear search to find the end of each sequence (once you know the beginning) will be vastly more efficient than using binary search.

But that's something that requires extra knowledge about the properties of the input array: we need to know k.

And this is when your "continuity" property comes into play!

Since the numbers are continuous, the last value in the array minus the first value in the array is equal to k-1, meaning that

k = array[n-1] - array[0] + 1

This rule can also be applied to any sub-array of your original array to calculate the variety metric for that sub-array.

That already gives you a very viable and efficient algorithm for finding the sequence: first perform a binary search for the beginning of the sequence, and then perform either binary or linear search depending on the relationship between n and k (or, even better, between the length of the right sub-array and the variety metric of the right sub-array).

P.S. The same technique can be applied to the first search as well. If you are looking for sequence of i, then you immediately know that it is the j-th sequence in the array, where j = i - array[0]. That means that the linear search for the beginning of that sequence will take j * n/k steps on average. If this value is smaller than log2(n), linear search might be a better idea than binary search.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

You can look at the start and the end elements to see how many elements k there are in the array and then do a modified binary search for each boundary, checking the element and its left and right. I don't think you could go faster than O(k log(n)).

If you search for the boundaries in order from left to right (or right to left) it ought to cut down the average time since you can search inside a smaller subset of the array, but I don't think that this affects the worst-case complexity.

That is, check the index i and its adjacent elements, searching for the 0-1 boundary:

|0|0|0|1|1|1|1|1|2|2|2
         \ i /

then go left:

|0|0|0|1|1|1|1|1|2|2|2
   \ i /

And since you found it, now look for the boundary between 1 and 2 in the set to the right of it:

1|1|1|1|1|2|2|2
    \ i /

1|1|1|1|1|2|2|2
        \ i /

And you're done, since you know how many boundaries you're looking for.

EDIT: Sorry, I didn't realize you only wanted one of the boundaries. The process is similar- You find the element you want to search for (which is O(log(n)) ) and then you search to the left and the right using the same modified search to check for the border. Depending on the overall size of the array vs the number of items in the array it might be faster in practice to only check on one side or the other.

Improve this answer

12 Comments

I didnt understand, I have to only find the boundaries of one particular integer , then why find all ?
The finding of 0-1 boundary should be same complexity as finding an integer. I think the complexity for finding the boundary would be O(log(n)) + O(log(n)); 1 for lower bound and 1 for upper bound.
O(log(n))+O(log(n)) is the same as O(log(n)).
@airza yes. but you have written O(k*log(n)); so what is k?
@user1416970 finding boundary is easy; instead of searching for x==seq[mid] try x==seq[mid] && x-1==seq[mid-1].
|
0

Your array is sorted, so you can used dichotomic search. Say n is the size of the array A, divide A in A1 and A2 with size (n/2) or respectively (n/2) and (n/2) + 1 if n is odd. Your are looking for the starting index of j. (j is in A)

 1. if A1(n/2) < j, then you know that j is in A2. 
 2. if A2(1) > j, then you know that j is in A1. 
 3. If A2(1) = j, then j may be in A1 and A2. Just check A1(n/2).
     if A1(n/2) < j then 2. Do the same recursively on A2 to find the last index
     else apply dichotomic search to find the starting index and ending index in both arrays
Improve this answer

1 Comment

This is exactly the modified binary search I had thought about using ! And similarly we can also find the ending index of the number.
0

Does it HAVE to be an algorithm? Your question just says find the positions, but if it is indeed meant to be some form of algorithmic approach let me know as I have provided a PHP function that deals with the matter in a fairly standard way.

$numbers = array(0,0,0,1,2,3,3,4,4,4,4);
function get_boundaries($array,$number)
{
    $keys = array_keys($array,$number);
    $found = count($keys);
    if($found == 0)
    {
        $ret = false;
    }
    else if($found == 1)
    {
        $ret = array($keys[0],$keys[0]);
    }
    else if($found > 1)
    {
        $ret = array($keys[0],$keys[$found-1]);
    }
    return $ret;
}

$result = get_boundaries($numbers,1);
print_r($result);


//Result when looking for 0
Array
(
    [0] => 0
    [1] => 2
)

//Result when looking for 1
Array
(
    [0] => 3
    [1] => 3
)

//Result when looking for 9
(boolean) false
Improve this answer

1 Comment

Thanks for the code but I was just thinking of ideas rather than looking for a code to the solution here. I meant to look for any ideas to the solution of the problem someone may have.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.