Re: [algogeeks] Re: searching a number in circular sorted array

[Rujin Cao]

Binary search is sufficient for this particular case.
To help the explain, we assume the circular sorted array is ascending if
probably rotated. we use *d[0..n - 1]* to represent the array
with n elements and *v* to represent the searched number.

Observing the circular sorted sequence d[0..n - 1]:
6  ,7,8   ,1   ,2   ,3  ,4,5
we can find that:
1) d[0] >= d[n - 1]
2) there exists one x that d[0..x] is ascending and d[x + 1.. n - 1] is also
ascending


Using the rules above, we can simply get an binary search algorithm:
The C++ code is below:

http://fayaa.com/code/view/20170/

*C++语言*: Codee#20170 
#include 

using namespace std;

// Parameters:
// @d: is one circularly sorted array, it looks like 6, 7, 8, 1, 2, 3, 5, 6
// @v: is the searched number
// Returns: -1 if not found or return the index
int BinarySearch(int d[], int len, int v)
{
if(d == NULL || len <= 0)
return -1;
int left = 0, right = len - 1;
while(right - left > 1)
{
int mid = (left + right) >> 1;
if(d[mid] >= d[left])
{
if(v >= d[mid])
left = mid;
else if(v >= d[left])
right = mid;
else
left = mid;
}
else // d[mid] < d[left]
{
if(v < d[mid])
right = mid;
else if(v < d[left])
left = mid;
else
right = mid;
}
}

if(d[left] != v)
return -1;
return left;
}

int main()
{
int d[] = {6, 7, 8, 1, 2, 3, 4, 5};

for(int i = 0; i < 10; i++)
{
printf("%d: %d\n", i, BinarySearch(d, 8, i));
}

return 0;
}





2011/6/11 L 

> Use ternary search to find the minimum number. (In this case 1)
> Then you have two sorted arrays, one ascending and one descending.
> Now, you can apply binary search. First, check the number with the
> last element and the first element and chose the appropriate array for
> searching.
>
> Time complexity: O(log n)
> Space complexity: O(1).
>
> On Jun 10, 9:06 pm, coder dumca  wrote:
> > hi frndz
> >
> > given an array which is circularly sorted  like
> >
> > 6  ,7,8   ,1   ,2   ,3  ,4,5
> >  search a  given number.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: searching a number in circular sorted array

[L]

Use ternary search to find the minimum number. (In this case 1)
Then you have two sorted arrays, one ascending and one descending.
Now, you can apply binary search. First, check the number with the
last element and the first element and chose the appropriate array for
searching.

Time complexity: O(log n)
Space complexity: O(1).

On Jun 10, 9:06 pm, coder dumca  wrote:
> hi frndz
>
> given an array which is circularly sorted  like
>
> 6  ,7    ,8   ,1   ,2   ,3  ,4    ,5
>  search a  given number.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.