Solved

binary search algorithm on a circular list

Posted on 2009-04-14
9
916 Views
Last Modified: 2013-11-12
hi,

heard this was a google interview question and had need to use it myself.  

if i have a circular, sorted list of n values x(0),  x(1), x(2), ..... x(n-1) , and given a value u, what is the index that satisfies
x(i) <= u < x(i+1)

iterative searching seems wasteful.  i'd use a binary search on this, but how do you handle the circular nature of it?  what do you do at the crossovers?  are there any c++ algorithms out there that do this?  

what would YOU do?

lou
0
Comment
Question by:ugeb
9 Comments
 
LVL 37

Accepted Solution

by:
gregoryyoung earned 250 total points
ID: 24140785
if its in an array just do an offset binary search, its just a matter of adjusting the index appropriately for a binary search.

take a look at how to calculate the length of a circular in an array, it has pretty much everything you need to do offsetitng.


if its in say a linked list ... google (pun intended) what a skip list is ...
0
 
LVL 15

Assisted Solution

by:spprivate
spprivate earned 250 total points
ID: 24140819
There is an IEEE article on doing a circular binary search

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=123386
0
 
LVL 11

Author Comment

by:ugeb
ID: 24140947
hey, thanx for those.


gregoryyoung: do you have any links to references?

spprivate:  i don't have an ieee account, is there a way to see article this without that?
0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 24141352
spprivate that article is not a simple binary search lol ... it looks like some link love from plugging keywords into a goodle search.

References? for which? is it an array or is it a linked list?

For an array do you really need one? its a simple arithmetic mapping to take the circular array and present it as 0-n. If you have a circular implementation just look at an index translation which is probably there already.

For a skip list http://en.wikipedia.org/wiki/Skip_list

Greg
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 11

Author Comment

by:ugeb
ID: 24142109
hi,

it's a list, but not a linked list ... i.e. an array, but a circular and sorted array.

without having to get as complicated as a skip list, how would you do a simple binary search on this and then handle the problem of not knowing where the end points are?

let's say the list (array) is
{ 7,8,9,10,11,12,1,2,3,4,5,6}

now i want to find out where 3 belongs.  if i split the array in half, half 1 will be sorted, but half 2 will contain a jump.  is there an efficient way to handle that?






0
 
LVL 3

Expert Comment

by:sprjp2
ID: 24143269
When you split the array, at least one half is sorted. You can find out which one by comparing its first and last element. In this way you can find the offset by which the array was shifted.
0
 
LVL 11

Author Closing Comment

by:ugeb
ID: 31570052
I was really hoping for more ideas and direction. Thanks.
0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 24160350
9 0 1 2 3      4 5 6 7 8
head = 1
tail = 0

3 4 5 6 7      8 9 0 1 2

head = 7
tail = 6


head and tail are both on the same side ... that side is offset

0 1 2 3 4     5 6 7 8 9
head = 0
tail = 9

both sides are sorted


If you later end up with neither head or tail in your segment you know that it is sorted continue as a normal binary search.


We know that we can do a normal binary search if we are on the sorted side. If we are not on the sorted side then we have to realize where our offset is

head->length = sorted
tail->start = sorted


From here we can keep with a binary search and just take the head/tail as a split point to figure out which one to search

we know that

start -> tail is sorted
and that head->length is sorted

so do some quick checks to see which of those ranges we fall into pick the one that we fall into and do a normal binary search ... If you only have one then pick that range (the rest is space you don't care about)



Hope this helps you in terms of more detail, I saw you commented on the question that you wanted more.

Greg
0
 
LVL 11

Author Comment

by:ugeb
ID: 24175936
hey,

thanks for the additional comment.  that's what I ended up doing, so i'm glad to know i was on the right track.

thanks again.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Scrum, Product Owner, and Daily Scrums 3 159
weak ssl ciphers 2 81
sumDigits  challenge 7 74
Java. Convert method from recursion based to iteration based ( loop based ) 6 71
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
Introduction This article explores the design of a cache system that can improve the performance of a web site or web application.  The assumption is that the web site has many more “read” operations than “write” operations (this is commonly the ca…
When you create an app prototype with Adobe XD, you can insert system screens -- sharing or Control Center, for example -- with just a few clicks. This video shows you how. You can take the full course on Experts Exchange at http://bit.ly/XDcourse.
I designed this idea while studying technology in the classroom.  This is a semester long project.  Students are asked to take photographs on a specific topic which they find meaningful, it can be a place or situation such as travel or homelessness.…

932 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now