binary search algorithm on a circular list

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?

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

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?

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.

I was really hoping for more ideas and direction. Thanks.

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