## Wednesday, September 23, 2015

### No. 58 - Search in Adjacent Numbers

Question: Given an array where two neighboring elements are adjacent (in absolute difference 1), can you write an algorithm to search an element in the array and return its position? If the element appears multiple times, please return the first occurrence.

For example, if given the array {4, 5, 6, 5, 6, 7, 8, 9, 10, 9} and an element 9, the element appears twice in the array, and the first occurrence is at position 7.

Analysis: The most simple and straightforward solution is to traverse the array and compare elements one by one. This strategy works for every array, and it does not utilize the property of the array where two neighboring elements are in absolute difference 1.

Let's try to search the first 9 from the array {4, 5, 6, 5, 6, 7, 8, 9, 10, 9}. Firstly we are at position 0 where the element 4 is. The difference between 9 and 4 is 5, so we move to the position 5. Why? Because the absolute difference between two neighboring elements is 1. If the numbers in the array is increasingly sorted, the element at position 5 is 9. If some elements decrease, 9 should sit on the right of position 5. Therefore, 5 is the leftmost possible position of the element 9.

It's 7 at position 5. The difference between 7 and 9 is 2, so we move to right by distance 2 to the position 7, where the first occurrence of 9 has been found.

We can summarize the solution: We begin from the first element of the element, and compare it with the given number. If the absolute difference is n, move to the right by distance n. Then we compare the current visited element. Repeat until the given element is found, or the position is beyond the length of the array when the given element is not available.

The solution can be implemented in C/C++ as below:

int findFirst(int* nums, int length, int target)
{

if (nums == nullptr || length <= 0)
return -1;

int index = 0;

while (index < length && nums[index] != target)
{

int delta = target - nums[index];
index += abs(delta);
}

if (index < length)
return index;

return -1;
}

The source code with unit test cases is shared at http://ideone.com/zuwjui.

More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. 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 article 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 the author via zhedahht@gmail.com . Thanks.

1. Hi Harry,

1. It seems that the example is incorrect since element 8 only appears once.
2. I'm interested in the time complexity of the solution.

Thanks again for this awesome post!

1. Thanks for your comment. It's a typo. It should be element 9 which appears twice.

2. I'm also curious about the time complexity, but have not figured out. Can anyone help?

3. Correct me if I'm wrong, if we have N numbers and the target number is T and the first number is F, then in the worst case, we may need N / |T - F| steps to reach it.

4. you can consider o(n) as an upper bound since worst case you need to check all the elements. best case will be if the array is sorted in reverse natural order eg 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. in that case if you're looking for 12, you will make 2, 4, 8... jumps so basically it's O(lg n)
so the complexity is somewhere between O(n) and O(lg n)

2. Hi Harry!

Did you figure out about the time complexity?

1. Hi Harry,

In debt to you for making my learning on the No. 58 - Search in Adjacent Numbers area so hassle-free! I lay my faith on your writings.

I have a small mailing list program running on an EC2 instance, Windows 2016 Server. Emails are send to my SES account which a daily limit well beyond what I'm sending.

The AWS Serverless Application Model (AWS SAM) extends AWS CloudFormation to provide a simplified way of defining the Amazon API Gateway APIs, AWS Lambda functions, and Amazon DynamoDB tables needed by your serverless application AWS Training .

But nice Article Mate! Great Information! Keep up the good work!

Regards,
Kevin

3. List of books to be referred for placement training preparation?
placement training center in chennai

4. Why not start at the middle of the array?

5. Hello my friend! I would like to tell you that this write-up is awesome, great written and include almost all important info. I recently came to know about http:www.yesiamhired.com, their Interview Tips are very effective.
Interview Tips

6. Integrated you software data at the best way of informatica system please call us on :- many new informatica interview questions references available online but this data warehouse interview questions one which is mentioned here is best in all possible ways. Always emphasize in getting this informatica questions

7. Valid reasons for leaving a job?
part-time jobs

8. Awesome information, brain exercising post..
Money Maker Research

9. Great article Lot's of information to Read... Great Man Keep Posting and update to People..Thanks
free online tests

10. Great information, containing all information and also has a great impact on the new technology. Its very helpful for me.

Word ending with letter..

12. Great information, containing all information and also has a great impact on the new technology. Its very helpful for me. Integrated you software data at the best way of informatica system.would like to tell you that this write-up is awesome, great written and include almost all important info.

Static code testing

13. Nice post http://www.selfcarinsurance.com

14. The time complexity is O(N). Assume the array is [4,3,4,3,4,3,4,3,...,4,3] and you are looking for 5. It is going to take you n/2 jumps whihc is O(n).

15. Hi There,

I am shocked, shocked, that there is such article exist!! But I really think you did a great job highlighting some of the key No. 58 - Search in Adjacent Numbers in the entire space.

I am a freelancer and I previously created an account using a gmail address and obtained my certification with this account. During the registration process of the APN program it needs a non gmail address so i used my professional address, how can i merge or link the certifications of my first account with the APN program?

Super likes !!! for this amazing post. I thinks everyone should bookmark this.

Thanks a heaps,
Preethi.

16. Szia,

In total awe…. So much respect and gratitude to you folks for pulling off such amazing blogs without missing any points on the No. 58 - Search in Adjacent Numbers. Kudos!

Should they be allowed to create ec2 and rds instances, iam user/groups, etc? Or should system admins create the infrastructure and just provide developers access to resources after?
AWS Training

Very useful article, if I run into challenges along the way, I will share them here.

Thanks a heaps,

17. Hi Buddie,

What you’re saying is absolutely correct No. 58 - Search in Adjacent Numbers , but this isn’t the exact situation everywhere. Where most smart folk work on a project - why can’t you do this the Boss asks :).

I have posted a few times a issue about a couple of resources in my account which can not be deleted through AWS Management Console. No answer up to now. AWS Training USA

Thank you very much and will look for more postings from you.

Irene Hynes

18. Thank you for sharing them! I hope you will continue to have similar posts to share with everyone!
- USPS Tracking

19. Wonderful article, very useful and well explanation. Your post is extremely incredible. I will refer this to my candidates...
Authorized ipad service center in Chennai | ipad service center in chennai | Authorized ipad service center in Chennai | ipad service center in chennai | ipad service center in chennai

20. PRBULLS - is a multi-platform media and content marketing company.
Content marketing is the publication of material designed to promote a brand, usually through a more oblique and subtle approach than that of traditional push advertising. Content marketing is most effective when it provides the consumer with accurate and unbiased information, the publisher with additional content and the advertiser with a larger audience and ultimately, a stronger brand…
Content Marketing Company

21. A bewildering web journal I visit this blog, it's unfathomably heavenly. Oddly, in this present blog's substance made purpose of actuality and reasonable. The substance of data is informative
Oracle Fusion Financials Online Training
Oracle Fusion HCM Online Training
Oracle Fusion SCM Online Training

22. I wanted to thank you for this great read. Your blog is one of the finest blog . Thanks for posting this informative article.
internship in indore

24. خدمة كتابة السيرة الذاتية الإحترافية says
Where to find best jobs in the world why not visit our website for jobs in saudi arabia other than saudi arabia you can look for jobs in pakistan and where you feel your cv is not professional feel free to use our Professional resume writing services we are here to help you out there in a world where completion is moving fast

25. Coding

Holiday Camps - Have fun with bricks while learning at the same time! Bricks 4 Kidz offers the best STEM and Coding Enrichment platform for your child. Join us now!

Coding

Holiday Camps - Have fun with bricks while learning at the same time! Bricks 4 Kidz offers the best STEM and Coding Enrichment platform for your child. Join us now!

26. Tula's International School Best Boarding School in Dehradun

Tula's International School Best Boarding School in Dehradun

Tula's International School Co-ed Boarding School in Dehradun

Tula's International School Best Residential School in Dehradun

Tula's International School Dehradun Boarding School Fee structure

Tula's International School Top Girls Boarding School India

Tula's International School Best CBSE Schools in Uttarakhand

Tula's International School Top Boarding Schools in India

Tula's International School MCA College in Dehradun

Tula's Institute Best Private BJMC College in Dehradun

27. content marketing for brands This was website contain many things to study, Thank you for sdharing this.

28. This article is a great article that I have seen in my blog career so far, it helps me a lot in Search in Adjacent Numbers, and will continue to do so in the future.

website development company in Surat Gujarat

29. Thank you for sharing very useful blog and for more information