Saturday, November 19, 2011

No. 22 - Turning Number in an Array


Problem: Turning number is the maximum number in an array which increases and then decreases. This kind of array is also named unimodal array. Please write a function which gets the index of the turning number in such an array.

For example, the turning number in array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is 10, so its index 5 is the expected output.

Analysis: As we know, the binary search algorithm is suitable to search a number in a sorted array. Since the input array for this problem is partially sorted, we may also have a try with binary search.

Let us try to get the middle number in an array. The middle number of array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is 5 (the fourth number). It is greater than its previous number 4, and less than its next number 10, so it is in the increasing sub-array. Therefore, numbers before 5 can be discarded in the next round of search.

The remaining numbers for the next round of search are {5, 10, 9, 8, 7, 6}, and the number 9 is in the middle of them. Since 9 is less than is previous number 10 and greater than its next number 8, it is in the decreasing sub-array. Therefore, numbers after 9 can be discarded in the next round of search.

The remaining numbers for the next round of search are {5, 10, 9}, and the number 10 is in the middle. It is noticeable that number 10 is greater than its previous number 5 and greater than its next number 9, so it is the maximum number. That is to say, the number 10 is the turning number in the input array.

We can see the process above is actually a classic binary search. Therefore, we can implement the required function based on binary search algorithm, as listed below:

int TurningNumberIndex(int* numbers, int length)
{
    if(numbers == NULL || length <= 2)
        return -1;

    int left = 0;
    int right = length - 1;
    while(right > left + 1)
    {
        int middle = (left + right) / 2;
        if(middle == 0 || middle == length - 1)
            return -1;

        if(numbers[middle] > numbers[middle - 1] &&
            numbers[middle] > numbers[middle + 1])
            return middle;
        else if(numbers[middle] > numbers[middle - 1] &&
            numbers[middle] < numbers[middle + 1])
            left = middle;
        else
            right = middle;
    }

    return -1;
}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks. 

11 comments:

  1. Replies
    1. In this case, is a pointer to integer vector.

      Delete
    2. Hi Harry,

      Brilliant article, glad I slogged through the No. 22 - Turning Number in an Array it seems that a whole lot of the details really come back to from my past project.

      I'm using CloudFormation and really enjoy it, but there are a couple of things which are lacking here. Auto scaling is a feature of AWS which enables you to configure and immediately provision and spin up new situations without any need of intervention AWS Tutorial . You need to do this by mounting thresholds and metrics to watch.

      Maybe there are some reasons why they weren't implemented here, but.

      So, the first thing is variables which can be populated during stack creation.
      Here is an example of similar service from another cloud provider:

      Thanks a lot. This was a perfect step-by-step guide. Don’t think it could have been done better.

      Shukran,
      Kevin

      Delete
  2. I think there is some redundant checking going on. The while condition ensures that you have at least 3 elements. So eg you don't need to check if middle == 0. For middle to be 0, we would need both right and left to be 0, or exactly one of right/left to be 1. But this fails the while loop condition.

    (Similarly for checking middle == length -1)

    ReplyDelete
  3. Great blog created by you. I read your blog, its best and useful information. You have done a great work. Super blogging and keep it up.
    php jobs in hyderabad.

    ReplyDelete
  4. • Nice and good article. It is very useful for me to learn and understand easily. Thanks for sharing your valuable information and time. Please keep updatingAzure Online course hyderabad

    ReplyDelete
  5. Hello There,


    Seems like I won the lottery here….This is a treasure box of blogs and your folks are like leprechauns! Phenomenal read on Turning Number in an Array!

    We have a t2.micro instance (built from amzn-ami-hvm-2016.09.1.20170119-x86_64-gp2) on which a customized Word Press is deployed. Following various posts here and elsewhere, various parameters for Apache and MySQL have been set to accommodate the 'size' of the host, including the deployment of a swap partition. The site has been running without issue for weeks.

    Please keep providing such valuable information.


    Shukran,
    Abhiram

    ReplyDelete
  6. Hi Harry,

    Hot! That was HOT! Glued to the No. 22 - Turning Number in an Array Held on 12 Jan 2011 your proficiency and style!

    Unfortunately, i revealed the access keys to my account by mistake on github yesterday evening which lead to unauthorized access. I got an email from AWS team notifying me the fraudulent activity yesterday and have followed the steps mentioned there. I have tried to terminate all unauthorized EC2 resources from my account.

    We can launch different types of instances from a single AMI. An instance type essentially determines the hardware of the host computer used for your instance AWS Tutorial . Each instance type offers different compute and memory capabilities.

    But great job man, do keep posted with the new updates.

    Regards,
    Kevin

    ReplyDelete
  7. Hi There,

    Hot! That was HOT! Glued to the No. 22 - Turning Number in an Array your proficiency and style!


    We are about to move four php apps to aws and I have some questions. AWS Training
    Since the ec2 instance would be a new from scratch, I do not really want to install a stuff what not that important. For example, Certbot (lets encrypt). The reason I don't want it on the main ec2 is because it does not work stable and very often it does not want to renew the certificates.
    What I thought: use a second ec2 just for updating the certificates. Replacing IP for 1-2 minutes once in 3 months is not a problem.

    Please keep providing such valuable information.

    Cheers,

    Radhey

    ReplyDelete
  8. Szia,

    Hot! That was HOT! Glued to the No. 22 - Turning Number in an Array your proficiency and style!


    We have a customer in Denmark whose legal department is asking for the physical address of the data center in which their data is being processed. The region/AZ in question would be eu-west-1a+b. Is there any chance AWS will disclose the address for this purpose? AWS Training USA

    I read multiple articles and watched many videos about how to use this tool - and was still confused! Your instructions were easy to understand and made the process simple.

    Thanks,
    Radhey

    ReplyDelete