fork(1) download 
  1. /**
  2. INPUT FORMAT:
  3. 	Line1 : array elements, seprated by space.
  4. 	Line 2: number, which is to be searched
  5.  
  6. **/
  7.  
  8. import java.util.Scanner;
  9.  
  10. class Main{
  11. 	public static void main(String args[]){
  12. 		Scanner sc = new Scanner(System.in);
  13. 	//	System.out.println("Enter array elements separted by space");
  14. 		String [] strArr = sc.nextLine().split(" ");
  15. 	//	System.out.println("Enter Number to find: ");
  16. 		int n = sc.nextInt();
  17. 		int[] arr = new int[strArr.length];
  18. 		for(int i=0;i<arr.length;i++){		// this is not O(n) .  Just for taking input & creating array :-)
  19. 			arr[i]= Integer.parseInt(strArr[i]);
  20. 		}
  21.  
  22. 		if (binSearchinRotatedArray(arr,n) )
  23. 			System.out.println("FOUND");
  24. 		else
  25. 			System.out.println("NOT FOUND");
  26. 	}
  27.  
  28. static boolean binSearchinRotatedArray(int arr[], int n){		// Actual program
  29. 		int start=0;
  30. 		int end = arr.length-1;
  31. 		int k=0;
  32.  
  33. 		while(start<=end){ // find the merging point of rotated element  O(log n )
  34.  
  35. 			k=(start+end)/2;
  36. 			if(arr[k]>arr[0]){	// first half already sorted
  37. 				start=k+1;
  38. 			}
  39. 			else
  40. 				end = k-1;	
  41. 		}
  42.  
  43. 		k=start;
  44. 		start=0;
  45. 		end = arr.length-1;
  46. 		System.out.println("k: "+k);
  47. 		return binSearch(arr, n, start, k-1) || binSearch(arr, n, k, end);    // O(log n) + O ( log n)
  48. 	}
  49.  
  50. 	static boolean binSearch(int arr[], int number, int start, int end) {		// binarySerach with given indices 
  51. 		int mid;
  52.  
  53. 		while(start<=end){   // do binary search  O(log n)
  54. 			mid = (start+end)/2;
  55.  
  56. 			if(arr[mid]> number)
  57. 				end=mid-1;
  58. 			else if(arr[mid]<number)
  59. 				start=mid+1;
  60. 			else		// element in found.
  61. 				return true;
  62. 		}
  63.  
  64. 		return false;
  65. 	}
  66.  
  67.  
  68.  
  69. }
Success #stdin #stdout 0.06s 213440KB
comments (?)
stdin 
7 8 9 1 2 3 4 5 6
1
stdout 
k: 3
FOUND
https://ideone.com/lN2og
language:
Java (HotSpot 12)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!