fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Ideone
  6. {
  7. 	// assuming ascending order a[0] <= a[1]
  8.     public static int find_first_index (int [] arr)
  9.     {
  10.         for(int i = 0; i < arr.length; i++)
  11.         {
  12.             if(arr[i] > arr[(i+1) % arr.length])
  13.             {
  14.                 return (i+1) % arr.length;
  15.             }
  16.         }
  17.  
  18.         return 0;
  19.     }
  20.  
  21. 	public static int startSearch(int a[], int x)
  22. 	{
  23. 		int f = find_first_index(a);
  24.  
  25. 		return search(a, f, 0, (a.length-1), x);
  26. 	}
  27.  
  28. 	public static int search(int a[], int f, int left, int right, int x)
  29. 	{
  30. 		int s = a.length;
  31. 	    int mid = (left + right) / 2;
  32. 	    if (x == a[(mid+f)%s]) { // Found element
  33. 	        return mid;
  34. 	    }
  35. 	    if (right < left) {
  36. 	        return -1;
  37. 	    }
  38.  
  39. 	    /* While there may be an inflection point due to the rotation, either the left or 
  40. 	     * right half must be normally ordered.  We can look at the normally ordered half
  41. 	     * to make a determination as to which half we should search. 
  42. 	     */
  43.  
  44. 	    if (a[(left+f)%s] < a[(mid+f)%s]) { // Left is normally ordered.
  45. 	        if (x >= a[(left+f)%s] && x < a[(mid+f)%s]) { 
  46. 	            return search(a, f, left, mid - 1, x);
  47. 	        } else {
  48. 	            return search(a, f, mid + 1, right, x);
  49. 	        }
  50. 	    } else if (a[(mid+f)%s] < a[(left+f)%s]) { // Right is normally ordered.
  51. 	        if (x > a[(mid+f)%s] && x <= a[(right+f)%s]) {
  52. 	            return search(a, f, mid + 1, right, x);
  53. 	        } else {
  54. 	            return search(a, f, left, mid - 1, x);
  55. 	        }               
  56. 	    } else if (a[(left+f)%s] == a[(mid+f)%s]) { // Left is either all repeats OR loops around (with the right half being all dups)
  57. 	        if (a[(mid+f)%s] != a[(right+f)%s]) { // If right half is different, search there
  58. 	            return search(a, f, mid + 1, right, x);
  59. 	        } else { // Else, we have to search both halves
  60. 	            int result = search(a, f, left, mid - 1, x); 
  61. 	            if (result == -1) {
  62. 	                return search(a, f, mid + 1, right, x); 
  63. 	            } else {
  64. 	                return result;
  65. 	            }
  66. 	        }
  67. 	    }
  68. 	    return -1;
  69. 	}
  70.  
  71.  
  72. 	public static void main (String[] args) throws java.lang.Exception
  73. 	{
  74. 		// your code goes here
  75. 	}
  76. }
Success #stdin #stdout 0.09s 321600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GiwW6N
language:
Java (12.0.1)
created:
7 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!