3. Search in Rotated sorted array

-

3. Search in Rotated sorted array


Problem link :- click here


package program;

public class Searching__3
{

	/*
	 	Search in a rotated sorted array 
	 			arr[] = {4, 5, 6, 7, 0, 1, 2, 3}      key = 0
	 			output : 4
	 	
	 	lets split the array into two parts 
	 	we have to find pivot for that 
	 	pivot means the element which is greater than its left and right element
	 	
	 	 we will find that element using binary search 
	 	 and see which array does the key belongs to and call
	 	 binary search to that array
	 */
	
	static int findPivot(int arr[], int low, int high)
	{
		if(low > high)
			return -1;
		if(high == low)
			return high;
		
		int mid = (low + high)/2;
		if( arr[mid-1] < arr[mid]    &&   arr[mid] > arr[mid+1] )
			return mid;
		else if( arr[mid] < arr[mid-1] )
			return findPivot(arr, low, mid-1);
		else if( arr[mid] < arr[mid+1] )
			return findPivot(arr, mid+1, high);
		
		return -1;
	}
	
	static int binarySearch(int arr[], int low, int high, int key)
	{
		int mid = (low+high)/2;
		
		if(arr[mid] == key)
			return mid;
		else if( key < arr[mid] )
			return binarySearch(arr, low, mid-1, key);
		else
			return binarySearch(arr, mid+1, high, key);
	}
	
	static int sortedRotatedSearch(int arr[], int n, int key)
	{
		int pivot = findPivot(arr, 0, n-1);
		
		if( key == arr[pivot] )
			return pivot;
		else if( key > arr[0] )
			return binarySearch(arr, 0, pivot, key);
		else
			return binarySearch(arr, pivot+1, n-1, key);
	}
	
	public static void main(String[] args)
	{
		int arr[] = {4, 5, 6, 7, 0, 1, 2, 3};
		int key = 6;
		
		int ans = sortedRotatedSearch(arr, arr.length, key);
		if(ans == -1)
			System.out.println("Not found");
		else
			System.out.println("Found at " + ans);
	}

}

Time complexity :- O()
Space complexity :- O()

Comments

Post a Comment

Popular posts from this blog

4.Sort an array of 0's, 1's & 2's.

-
Image
4.Sort an array of 0's, 1's & 2's. Problem link :- click here C code #include<stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } void sort_012(int A[], int n) { int i, j, m; i = 0; j = n-1; m = 0; while(m<=j) { if(A[m] == 0) { swap(&A[i], &A[m]); i++; m++; } else if(A[m] == 1) { m++; } else { swap(&A[j], &A[m]); j--; } } } void main() { int arr[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array(only 0, 1, or 2)\n"); for(i=0; i<n; i++) scanf("%d",&arr[i]); printf("Given Array\n"); for(i=0; i<n; i++) printf("\t%d",arr[i]); printf("\n...
Read more

1. Reverse

-
Image
1. Reverse the Array.   Problem link :- Reverse the array Algorithm idea :- C code //Reverse the array #include<stdio.h> void rev_arr(int arr[], int start, int end) { int temp; while(start < end) { temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } void print_arr(int arr[], int size) { int i; for(i=0; i<size; i++) printf("\t%d",arr[i]); printf("\n"); } void main() { int arr1[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array\n"); for(i=0; i<n; i++) scanf("%d",&arr1[i]); printf("Array before reversing\n"); print_arr(arr1, n); rev_arr(arr1, 0, n-1); printf("\nArray after reversing\n"); print_arr(arr1, n); } Java code //Reverse the array package programs;...
Read more

3. Height of Binary tree

-
3. Height of Binary tree Problem link :- click here package Binary_Tree; public class BinaryTree__3 { static int heightOfTree(Node root) { if(root == null) return 0; int left_height = heightOfTree(root.left); int right_height = heightOfTree(root.right); return Math.max(left_height, right_height) + 1; } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); int arr[] = {2, -1, 3, -1, -1, 3}; tree.root = tree.createTree(arr, 0); int ans = heightOfTree(tree.root); System.out.println("Height : " + ans); } } Time complexity :- O(n) Space complexity :- O(n)
Read more