469,582 Members | 2,425 Online

# Rotated Sorted list

Question :An element in a sorted list can be found in O(log n) time via
binary search. But suppose I rotate the sorted list at some pivot
unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4
5 1 2. Now devise a way to find an element in the rotated list in O(log
n) time.

Once the position of the pivot element(least element)is known things
will be easy.
I'm not able to correct the following piece of code(which finds the
pivot element's position) to make it work properly.
Please suggest ways in which i can do it.

int findPivot(int arr[], int n)
{
int low = 0, high = n-1, mid;
while(low <= high)
{
mid = (low + high) / 2;
if(arr[low] < arr[mid])
low = mid + 1;
else if (arr[mid] < arr[high])
high = mid-1;
else
return mid;
}
return -1;
}

Please suggest me ways in which i can modify this to work for finding
the pivot element.

Regards,
Rajesh

Feb 1 '06 #1
8 1970 Rajesh wrote:
Question :An element in a sorted list can be found in O(log n) time via
binary search. But suppose I rotate the sorted list at some pivot
unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4
5 1 2. Now devise a way to find an element in the rotated list in O(log
n) time.

Once the position of the pivot element(least element)is known things
will be easy.
I'm not able to correct the following piece of code(which finds the
pivot element's position) to make it work properly.
Please suggest ways in which i can do it.

int findPivot(int arr[], int n)
I'd rather use
int findPivot (const int *arr, int size)
or even
size_t findPivot (const int *arr, size_t size)
{
int low = 0, high = n-1, mid;
while(low <= high)
{
mid = (low + high) / 2;
if(arr[low] < arr[mid])
low = mid + 1;
else if (arr[mid] < arr[high])
high = mid-1;
Can this case occur?
else
return mid;
}
return -1;
}

Please suggest me ways in which i can modify this to work for finding
the pivot element.

As I am not sure how much of this is homework:
- printf() the indices, elements and decisions.
- rethink the whole thing:
if arr <= arr[n - 1], there cannot be a pivot
otherwise, for your array, there must always hold
arr[low] > arr[high]
arr[pivot-1] > arr[pivot] (be careful to try this right)
Take care of n <= 2 (or think about how the above could take
care of it).

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Feb 1 '06 #2
Rajesh wrote:
Question :An element in a sorted list can be found in O(log n) time via
binary search. But suppose I rotate the sorted list at some pivot
unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4
5 1 2. Now devise a way to find an element in the rotated list in O(log
n) time.

Are all elements unique? If there is no restriction on repetitions,
consider the list {2 2 ... 2 3 1 2 2 ... 2}. Can the pivot be found in
O(log n)?

Answer those questions first, then propose a technique.

--
Feb 3 '06 #3
Ya all the numbers are unique. Can you suggest ways to correct this
logic?

Thanks,
Rajesh

Feb 3 '06 #4
"Rajesh" <ra***********@gmail.com> writes:
Ya all the numbers are unique. Can you suggest ways to correct this
logic?

What??

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Feb 3 '06 #5
Rajesh wrote:
Ya all the numbers are unique. Can you suggest ways to correct this
logic?

The logic doesn't need correction, it needs to be determined. So far
you have refused to show your own effort at solving the problem. A good
place to start is try it with pencil and paper, thinking about which
items to compare.

--
Feb 3 '06 #6
Rajesh wrote:

Question :An element in a sorted list can be found in O(log n) time via
binary search. But suppose I rotate the sorted list at some pivot
unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4
5 1 2. Now devise a way to find an element in the rotated list in O(log
n) time.

Once the position of the pivot element(least element)is known things
will be easy.
I'm not able to correct the following piece of code(which finds the
pivot element's position) to make it work properly.
Please suggest ways in which i can do it.

int findPivot(int arr[], int n)

Split the array into an upper half and a lower half.
If neither half is disordered,
then the pivot is the base of the upper half.
Otherwise the pivot is located in the disordered half,
which is where the pivot search should continue.

/* BEGIN new.c */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int comparison(const void *arg1, const void *arg2);
void *findPivot(const void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

int main(void)
{
char array[] = "7890123456";
char copy[sizeof array];
char *pivot;

printf("char array = \"%s\";\n\n", array);
strcpy(copy, array);
printf("Value %s\n", copy);
qsort(copy, sizeof copy - 1, sizeof *copy, comparison);
printf("Index %s\n", copy);
pivot = findPivot
(array, sizeof array - 1, sizeof *array, comparison);
printf("\nThe pivot is array[%d] and is '%c'\n",
(int)(pivot - array), *pivot);
return 0;
}

int comparison(const void *arg1, const void *arg2)
{
return *(char *)arg1 - *(char *)arg2;
}

void *findPivot(const void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t half;
const unsigned char *array;

array = base;
while (compar(array, array + size * (nmemb - 1)) > 0) {
half = nmemb / 2;
if (compar(array, array + size * (half - 1)) > 0) {
nmemb = half;
} else {
if (compar(
array + size * half,
array + size * (nmemb - 1)) > 0)
{
array += half * size;
nmemb -= half;
} else {
array += size * half;
break;
}
}
}
return (void *)array;
}

/* END new.c */

--
pete
Feb 3 '06 #7
pete wrote:
Rajesh wrote:
Question :An element in a sorted list can be found in O(log n) time via
binary search. But suppose I rotate the sorted list at some pivot
unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4
5 1 2. Now devise a way to find an element in the rotated list in O(log
n) time.

Once the position of the pivot element(least element)is known things
will be easy.
I'm not able to correct the following piece of code(which finds the
pivot element's position) to make it work properly.
Please suggest ways in which i can do it.

int findPivot(int arr[], int n)
Split the array into an upper half and a lower half.
If neither half is disordered,
then the pivot is the base of the upper half.

Why not the base of the lower half?
Otherwise the pivot is located in the disordered half,
which is where the pivot search should continue.

/* BEGIN new.c */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int comparison(const void *arg1, const void *arg2);
void *findPivot(const void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

int main(void)
{
char array[] = "7890123456";
char copy[sizeof array];
char *pivot;

printf("char array = \"%s\";\n\n", array);
strcpy(copy, array);
printf("Value %s\n", copy);
qsort(copy, sizeof copy - 1, sizeof *copy, comparison);
printf("Index %s\n", copy);
pivot = findPivot
(array, sizeof array - 1, sizeof *array, comparison);
printf("\nThe pivot is array[%d] and is '%c'\n",
(int)(pivot - array), *pivot);
return 0;
}

int comparison(const void *arg1, const void *arg2)
{
return *(char *)arg1 - *(char *)arg2;
}

void *findPivot(const void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t half;
const unsigned char *array;

array = base;
while (compar(array, array + size * (nmemb - 1)) > 0) {
half = nmemb / 2;
if (compar(array, array + size * (half - 1)) > 0) {
nmemb = half;
} else {
if (compar(
array + size * half,
array + size * (nmemb - 1)) > 0)
{
array += half * size;
nmemb -= half;
} else {
array += size * half;
break;
}
}
}
return (void *)array;
}

/* END new.c */

Since Rajesh didn't receive the benefit of working out something
himself, I offer him (and others) the following problems for bonus points!

1. Assuming CHAR_MAX < INT_MAX, which line(s) in findPivot will not be
executed for any possible initial char values in array?

2. Given the above code and initialized array, what perverted compare()
function (with no side effects) will cause findPivot to either loop
indefinitely or generate an invalid pointer?

--
Feb 4 '06 #8

pete wrote:
Rajesh wrote:
Question :An element in a sorted list can be found in O(log n) time via
binary search. But suppose I rotate the sorted list at some pivot
unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4
5 1 2. Now devise a way to find an element in the rotated list in O(log
n) time.

Once the position of the pivot element(least element)is known things
will be easy.
I'm not able to correct the following piece of code(which finds the
pivot element's position) to make it work properly.
Please suggest ways in which i can do it.

int findPivot(int arr[], int n)
Split the array into an upper half and a lower half.
If neither half is disordered,
then the pivot is the base of the upper half.

Why not the base of the lower half?
Otherwise the pivot is located in the disordered half,
which is where the pivot search should continue.

/* BEGIN new.c */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int comparison(const void *arg1, const void *arg2);
void *findPivot(const void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

int main(void)
{
char array[] = "7890123456";
char copy[sizeof array];
char *pivot;

printf("char array = \"%s\";\n\n", array);
strcpy(copy, array);
printf("Value %s\n", copy);
qsort(copy, sizeof copy - 1, sizeof *copy, comparison);
printf("Index %s\n", copy);
pivot = findPivot
(array, sizeof array - 1, sizeof *array, comparison);
printf("\nThe pivot is array[%d] and is '%c'\n",
(int)(pivot - array), *pivot);
return 0;
}

int comparison(const void *arg1, const void *arg2)
{
return *(char *)arg1 - *(char *)arg2;
}

void *findPivot(const void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t half;
const unsigned char *array;

array = base;
while (compar(array, array + size * (nmemb - 1)) > 0) {
half = nmemb / 2;
if (compar(array, array + size * (half - 1)) > 0) {
nmemb = half;
} else {
if (compar(
array + size * half,
array + size * (nmemb - 1)) > 0)
{
array += half * size;
nmemb -= half;
} else {
array += size * half;
break;
}
}
}
return (void *)array;
}

/* END new.c */

Since Rajesh didn't receive the benefit of working out something
himself,
I offer him (and others) the following problems for bonus points!

1. Assuming CHAR_MAX < INT_MAX, which line(s) in findPivot will not be
executed for any possible initial char values in array?

I rewrote findPivot.

void *findpivot(const void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t half;
const unsigned char *array;

array = base;
while (compar(array, array + size * (nmemb - 1)) > 0) {
half = nmemb / 2;
if (compar(array, array + size * (half - 1)) > 0) {
nmemb = half;
} else {
array += size * half;
nmemb -= half;
}
}
return (void *)array;
}
2. Given the above code and initialized array,
what perverted compare()
function (with no side effects) will cause findPivot to either loop
indefinitely or generate an invalid pointer?

--
pete
Feb 4 '06 #9

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

 57 posts views Thread by Egor Bolonev | last post: by 6 posts views Thread by rzed | last post: by 10 posts views Thread by Der Andere | last post: by 3 posts views Thread by Andrew Clark | last post: by 6 posts views Thread by charsh | last post: by 1 post views Thread by J L | last post: by 1 post views Thread by rajesh_krec | last post: by 4 posts views Thread by shrishjain | last post: by 2 posts views Thread by Tilo Pätzold | last post: by reply views Thread by suresh191 | last post: by reply views Thread by goatbishop | last post: by reply views Thread by Marketing QM | last post: by 1 post views Thread by strativab | last post: by 11 posts views Thread by MGadAllah | last post: by reply views Thread by allessa | last post: by 1 post views Thread by Samuh | last post: by reply views Thread by hefaz | last post: by reply views Thread by billypeterson | last post: by