fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		// your code goes here
  13. 	}
  14.  
  15. 	public void findInRotatedSortedArray(int[] arr, int target) {
  16.         int n = arr.length;
  17.         int low = 0, high = n - 1, maxVal = Integer.MIN_VALUE, maxIdx = -1, minVal = Integer.MAX_VALUE, minIdx = -1;
  18.  
  19.         //to check if the array is already sorted
  20.         if (arr[low] < arr[high]) {
  21.             binarySearch(0, n - 1, arr, target);
  22.         }
  23.  
  24.         while (low <= high) {
  25.             int mid = (low + high) / 2;
  26.  
  27.             if (arr[mid] > arr[n - 1]) {
  28.                 //value is on the left side
  29.                 //now to find if that value is max value in arr
  30.  
  31.                 if (mid > 0 && mid < n - 1) {
  32.                     if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
  33.                         maxVal = arr[mid];
  34.                         maxIdx = mid;
  35.                         minVal = arr[mid + 1];
  36.                         minIdx = mid + 1;
  37.                     } else {
  38.                         low += mid + 1;
  39.                     }
  40.                 }
  41.             } else {
  42.                 if (mid > 0 && mid < n - 1) {
  43.  
  44.                     //to find the min value in arr
  45.                     if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
  46.                         minVal = arr[mid];
  47.                         minIdx = mid;
  48.                         maxVal = arr[mid - 1];
  49.                         maxIdx = mid - 1;
  50.                     } else {
  51.                         high = mid - 1;
  52.                     }
  53.                 }
  54.             }
  55.         }
  56.  
  57.         if (target > minVal && target > arr[n - 1]) {
  58.             binarySearch(0, maxIdx, arr, target);
  59.         } else {
  60.             binarySearch(minIdx, n - 1, arr, target);
  61.         }
  62.     }
  63.  
  64.     private void binarySearch(int low, int high, int[] arr, int target) {
  65.     }
  66. }
Success #stdin #stdout 0.06s 52636KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IX9RjX
language:
Java (HotSpot 12)
created:
13 hours 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!