CODEWITHSUNDEEP
arraysalgorithmsorting
Subham Tripathi
Subham Tripathi

Reputation: 2733

Searching in an array that is first decreasing and then increasing

I have a array that is in descending order initially. Now i traverse to a random index in my array and after that point i flip the list so that the rest of the list become ascending.

Now a number is given and its index needs to be find. what is an efficient algorithm to find the index of the given number?

e.g :

Initial list : 50 48 21 15 9 8 7 5 3 2 1

After Flipping at number 9: 50 48 21 15 1 2 3 5 7 8 9

Provided number : 21

Index of 21 : ?

Edit 1: It is interesting to note that the minimum value element of the list in desc order will always be greater than the maximum value element of list in ascending order as it was intially part of the list in desc order.

Upvotes: 3

Views: 9849

Answers (4)

user3922145
user3922145

Reputation: 39

let i=0, n be the length, m= n/2, and x be the number to search and the array be myArray[] 

IF x> Array[n-1]
{

LABEL 1 

  IF myArray[m] < myArray[m+1] 
  { 
    Here we are in the ascendind order and x is not here since x> myArray[n-1]  
    Set n=m and m=n/2  and GOTO LABEL 1.
  }  
  ELSE  
  {  
    Means we are in the descending order.  
    IF x>myArray[m]
    {
      Means x is b/n myArray[0] and myArray[m] therefore, perform binary search in   
    }  
    ELSE
    {
      Means x is b/n myArray[m] and myArray[n-1]
      therefore, set i=m, m=(n-i)/2 and GOTO LABEL 1.  
    }  
  }  
ELSE

LABEL 2

{  
  IF myArray[m] < myArray[m+1]
  {   
    IF 
    {  
      x < myArray[m] set n=m, m=n/2 and GOTO label 2
    } 
    ELSE  
    {  
      perform binary search b/n myArray[m] and myArray[n-1]    
    } 
  } 
  ELSE
  {  
    set i=m, m=n-i/2 and GOTO LABEL 2 
  } 
}

Upvotes: 0

chiastic-security
chiastic-security

Reputation: 20520

This is the inverse of this question and answer, where the sequence goes up and then down again. In yours, it goes down and then back up.

The key is to start by finding the index of the minimum element. Once you have that, you can do a binary search in the left-hand (decreasing) part, and a binary search in the right-hand (increasing) part. Since the binary searches can be done in log time, you can do the whole thing in log time provided that you can find the minimum element in log time.

Fortunately you can also do that with a binary search. For any place in the array that you consider, if the following element is greater, then you're in the right-hand (increasing) part; and if it's smaller, then you're in the left-hand (decreasing) part. This is enough to allow you to perform a binary search to find the minimum.

Upvotes: 4

user3922145
user3922145

Reputation: 39

Let the length of your array be n in your case 13
the random index(flip point) be m in your case 4
and the number to be searched be x in your case 21

If x>= value at index m-1 // in your case 21>=15 true
then use binary search for the part of the array from index 0 to m-1
Else
use binary search for the part of the array from index m to n-1

Note: After flipping you will have the array being half descending from 0 to flipping point and half ascending from flipping point to the end of the array.

Upvotes: 0

Sherry
Sherry

Reputation: 269

Here you go.. 

var source = Enumerable.Range(1, 100).Cast<int?>().ToArray();
var destination = new int?[source.Length];

var s = new Stopwatch();
s.Start();
for (int i = 0; i < 1000000;i++)
{
Array.Copy(source, 1, destination, 0, source.Length - 1);
}
s.Stop();
Console.WriteLine(s.Elapsed);

Here are the performance results for 1 million iterations of each solution (8 Core Intel Xeon E5450 @ 3.00GHz)

                            100 elements    10000 elements
For Loop                     0.390s         31.839s 
Array.Copy()                 0.177s         12.496s
Aaron 1                      3.789s         84.082s
Array.ConstrainedCopy()      0.197s         17.658s

Upvotes: -2

Related Questions