binary search in sorted rotated array

Problem Given a Sorted Array which can be rotated find an Element in it in minimum Time Complexity.

#include <iostream>
#include <assert.h>

int binary_search( int arr[], int low, int high, int target) {
	while ( low <= high ) {

		int mid =  ( low + high ) / 2 ;

		if (target == arr[mid] )
			return mid;

		if ( target < arr[mid] ) 
			high = mid - 1;
		else 
			low = mid + 1;
	}
	return -1;
}
int binary_search_rotation( int arr[], int rotation, int target, int size ) {
	int rc = -1;
	if ( target == arr[rotation - 1] ) {
		rc = rotation - 1;
	} else if ( target < arr[rotation - 1] && target >= arr[0]) {
		rc = binary_search( arr, 0, rotation - 1, target);
	} else  {
		rc = binary_search(arr, rotation, size , target );
	}
	return rc;
}

int main ( int argc, char **argv) {
	int arr[] ={6,7,8,9,10,1,2,3,4,5};
	int rot_cnt = 5;
	int target = 9;
	int result = 0;

	for ( int idx = 0; idx < 10; idx++ ) {		
		int target = arr[idx];
		assert ( binary_search_rotation(arr,5, target, 10) == idx );	
	}

	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s