CareerCup

Binary search

int rotation_index(const vector<int>& arr, int range_start, int range_end) {
  if (arr.size() < 2) return 0;
  if (range_end - range_start <= 1) return range_start;

  int first = arr[0];
  int mid = (range_start+range_end)/2; 

  int prev_elem = arr[mid];
  if (mid < first) return rotation_index(arr, range_start, mid)
  else if (mid > first) return rotation_index(arr, mid, range_end);
}

Binary Search based algo.
Java Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Arrays;


public class SearchMinIndexInRotatedSortedArray {

    public static int search(List<Integer> a,int lo, int hi){
        
        int mid = ( lo + hi) >>> 1;
        if( hi - lo == 1){
            if(a.get(lo) < a.get(hi))
                return lo;
            else 
                return hi;
        }
        else if( hi == lo){
            return hi;
        }
        
        if( a.get(lo) <= a.get(mid)){
                        if( a.get(mid) <= a.get(hi) ){
                            return lo;
                        }
                        else{
                return search(a, mid, hi);
                        }
        }
        else{
            return search(a, lo, mid);
        }
    }
    
    public static void main(String[] args){
        List<Integer> a = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9,10));
        List<Integer> b = null;
        b = new ArrayList<Integer>();

        for(int i=0;i< a.size(); i++){
            b.clear();
            b.addAll(a);
            Collections.rotate(b, i);
            System.out.println("Searching in: " + b + " index of min: " + search(b, 0, b.size()-1));
        }
    }
}

Output of above program:
Searching in: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] index of min: 0
Searching in: [10, 1, 2, 3, 4, 5, 6, 7, 8, 9] index of min: 1
Searching in: [9, 10, 1, 2, 3, 4, 5, 6, 7, 8] index of min: 2
Searching in: [8, 9, 10, 1, 2, 3, 4, 5, 6, 7] index of min: 3
Searching in: [7, 8, 9, 10, 1, 2, 3, 4, 5, 6] index of min: 4
Searching in: [6, 7, 8, 9, 10, 1, 2, 3, 4, 5] index of min: 5
Searching in: [5, 6, 7, 8, 9, 10, 1, 2, 3, 4] index of min: 6
Searching in: [4, 5, 6, 7, 8, 9, 10, 1, 2, 3] index of min: 7
Searching in: [3, 4, 5, 6, 7, 8, 9, 10, 1, 2] index of min: 8
Searching in: [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] index of min: 9

int FindIndexOfRotation(int a[],int start,int end)
{
	if(start == end-1)
	{
		if(a[start]<a[end])return start;
		return end;
	}
	int mid=(start+end)>>1;
	if(a[start]<a[mid])
	{
		if(a[start]<a[end])
			return start;
		else
			return FindIndexOfRotation(a,mid,end);
	}
	else if(a[mid]<a[end])
	{
		return FindIndexOfRotation(a,start,mid);
	}
	else
		return mid;
}
let me know any bug in this

Rotation happened at the index where i-1 > i+1

Use binary search technique and find index i for which value of i-1 is greater

public class pivotSearch{

public static void main(String [] args)
{
int []arr={4,5,6,7,8,9,10,11,12,13,1,2,3};
int ind=piv(arr,0,arr.length-1);
int key=10;
System.out.println("The array is pivoted at :"+arr[ind]+" index: "+ind);
System.out.println("The array contains :"+key+" at "+pivotedSearch(arr,key,ind));
}

public static int pivotedSearch(int []data,int key,int pivot)
{
if(data[pivot]==key) return pivot;
else if(key>data[0])	
	return binSearch(data,key,0,pivot-1);
else
	return binSearch(data,key,pivot+1,data.length-1); 
}

public static int binSearch(int []data,int key,int low,int high)
{
int mid=(low+high)/2;
if(low>high) return -1;
if(data[mid]==key) return mid;
else if(data[mid]<key) return binSearch(data,key,mid+1,high);
else return binSearch(data,key,low,mid-1);
}


public static int piv(int []data,int low,int high)
{
int mid=(low+high)/2;
if(low>high) return -1;

if(data[mid]>data[mid+1])
	{
		return mid+1;
	}
else if(data[low]>data[high])
	{
		return piv(data,mid+1,high);
	}
else	{
		return piv(data,low,mid-1);
	}
}

}

int FindIndexOfRotation(int a[],int start,int end)
{
	if(start == end-1)
	{
		if(a[start]<a[end])return start;
		return end;
	}
	int mid=(start+end)>>1;
	if(a[start]<a[mid])
	{
		if(a[start]<a[end])
			return start;
		else
			return FindIndexOfRotation(a,mid,end);
	}
	else if(a[mid]<a[end])
	{
		return FindIndexOfRotation(a,start,mid);
	}
	else
		return mid;
}
let me know if there is any bug in this

it is sufficient to find the Minimum element of the array as its position tells how many times array is rotated...the code is following

public int rotate(int[] arr){
	int min=arr[0];
	int i;
	for(i=0;i<arr.length;i++){
		if(arr[i]<min){
			min=arr[i];			
		}
	}
	return i;
}

is so there a truly working solution for O(log n) time and be able to cover the corner cases like: {2, 8, 9, 1, 2, 2} ??

Isn't the solution kinda simple?
Just go through the array and find where a[ i ]<a[ i+1 ]
Wherever the condition is satisfied, index = ( a.length - i ) + 1
Or am I missing the basic concept of rotating a sorted array? -_-

def rotationIndex(a: Array[Int]): Int = {
 val len = a.length-1
 var curr = 0
 val frst = a(0)
 var nxt = a(1)
 var asc = true
 if(frst != nxt){
  asc = if(nxt < frst) false else asc
 }else {
  var i = 1
  while(frst == nxt && len >= i){
   i = i+1
   nxt = a(i)
  }
  asc = if(nxt < frst) false else asc
 }
 if(asc){
  while(a(curr) < a(curr+1)){
   curr = curr+1
  }
 }else {
   while(a(curr) > a(curr+1)){
   curr = curr+1
  }
 }
  curr
}

// Using Java

public int rotateArrayRetRotIndex(Object[] arr)
{
	int mid = arr.length / 2;
	for(int i = 0; i < mid; i++)
	{
		int tempVal = arr[i];
		arr[i] = arr[arr.length - 1 - i];
		arr[arr.length - 1 - i]  = tempVal;
	}
	return mid;
}