Rotated Sorted list

[Rajesh]

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

 

[Michael Mair]

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[0] <= arr[n - 1], there cannot be a pivot
otherwise, for your array, there must always hold
arr[low] > arr[high]
and for your pivot element
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

 

[Thad Smith]

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.

 

[Rajesh]

Ya all the numbers are unique. Can you suggest ways to correct this
logic?

Thanks,
Rajesh

 

[Keith Thompson]

Ya all the numbers are unique. Can you suggest ways to correct this
logic?

What??

<http://cfaj.freeshell.org/google/>

 

[pete]

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[10] = \"%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 */

 

[Thad Smith]

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.

 

[Thad Smith]

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[10] = \"%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?

 

[pete]

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[10] = \"%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;
}