DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Puzzles && Algorithms
*****************************************************
#Post#: 25--------------------------------------------------
search an element in a sorted array
By: dinesh Date: August 16, 2012, 10:13 am
---------------------------------------------------------
Question:
An element in a sorted array can be found in O(log n) time via
binary search. But suppose I rotate the sorted array at some
pivot unknown to you beforehand. So for instance, 1 2 3 4 5
might become 3 4 5 1 2. Devise a way to find an element in the
rotated array in O(log n) time.
#Post#: 30--------------------------------------------------
Re: search an element in a sorted array
By: kranthipls Date: August 17, 2012, 2:40 am
---------------------------------------------------------
@Dinesh: I did not understand about the rotation part clearly.
Can you explain with two more examples like take 2 or 3 as pivot
and tell me the output
#Post#: 48--------------------------------------------------
Re: search an element in a sorted array
By: dinesh Date: August 23, 2012, 1:22 am
---------------------------------------------------------
if the pivot is 3,
then the array becomes 4 5 1 2 3
if pivot is 2,
then the array is 3 4 5 1 2
#Post#: 65--------------------------------------------------
Re: search an element in a sorted array
By: kranthipls Date: August 27, 2012, 10:20 am
---------------------------------------------------------
@Dinesh Please post the answer.
#Post#: 66--------------------------------------------------
Re: search an element in a sorted array
By: dinesh Date: August 27, 2012, 10:25 pm
---------------------------------------------------------
Algorithm:
Find the pivot point, divide the array in two sub-arrays and
call binary search.
The main idea for finding pivot is – for a sorted (in increasing
order) and pivoted array, pivot element is the only only element
for which next element to it is smaller than it.
Using above criteria and binary search methodology we can get
pivot element in O(logn) time :P
Input arr[] = {3, 4, 5, 1, 2}
Element to Search = 1
1) Find out pivot point and divide the array in two
sub-arrays. (pivot = 2) /*Index of 5*/
2) Now call binary search for one of the two sub-arrays.
(a) If element is greater than 0th element then
search in left array
(b) Else Search in right array
(1 will go in else as 1 < 0th element(3))
3) If element is found in selected sub-array then return index
Else return -1.
Implementation:
/*Program to search an element in a sorted and pivoted array*/
#include <stdio.h>
int findPivot(int[], int, int);
int binarySearch(int[], int, int, int);
/* Searches an element no in a pivoted sorted array arrp[]
of size arr_size */
int pivotedBinarySearch(int arr[], int arr_size, int no)
{
int pivot = findPivot(arr, 0, arr_size-1);
if(arr[pivot] == no)
return pivot;
if(arr[0] <= no)
return binarySearch(arr, 0, pivot-1, no);
else
return binarySearch(arr, pivot+1, arr_size-1, no);
}
/* Function to get pivot. For array 3, 4, 5, 6, 1, 2
it will return 3 */
int findPivot(int arr[], int low, int high)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if(arr[mid] > arr[mid + 1])
return mid;
if(arr[low] > arr[mid])
return findPivot(arr, low, mid-1);
else
return findPivot(arr, mid + 1, high);
}
/* Standard Binary Search function*/
int binarySearch(int arr[], int low, int high, int no)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if(no == arr[mid])
return mid;
if(no > arr[mid])
return binarySearch(arr, (mid + 1), high, no);
else
return binarySearch(arr, low, (mid -1), no);
}
/*Return -1 if element is not found*/
return -1;
}
/* Driver program to check above functions */
int main()
{
int arr[10] = {3, 4, 5, 6, 7, 1, 2};
int n = 5;
printf("Index of the element is %d", pivotedBinarySearch(arr,
7, 5));
getchar();
return 0;
}
Time Complexity O(logn)
*****************************************************