CareerCup

Actually, you can do a little simpler than that. You don't actually need the pivot index. We just need to compare the mid element with rightmost and leftmost elements. If mid element is larger than leftmost element, bottom half of the array is properly sorted. In this case, we have a plain binary search (if element we are searching for is between leftmost and middle element, look at the lower half of the array; otherwise look at the upper half of the array).
If mid element is smaller than leftmost element, upper half of the array is sorted. Accordingly, we look if the given element is at the upper of lower part.

int search(int A[], int N, int key) {
  int left = 0;
  int right = N - 1;
 
  while (left <= right) {
 
    int mid = left + ((right-left) / 2);
    if (A[mid] == key) return mid;
 
    // the bottom half is sorted
    if (A[left] <= A[mid]) {
      if (A[left] <= key && key < A[mid])
        right = mid -1;
      else
        left = mid+1;
    }
    // the upper half is sorted
    else {
      if (A[mid] < key && key <= A[right])
        left = mid+1;
      else
        right = mid-1;
    }
  }
  return -1;
}

The method won't work if there are duplicates in the array

I would use Ternary Search to find the pivot and then a normal Binary Search, knowing the pivot. The time complexity is O(log n) if the values are distinct

int FindPivot(int v[], int size) { // ternary search to find the pivot
    int left = 0, right = size-1;
    while (left+1 < right) {
        int c1 = (left*2 + right) / 3;
        int c2 = (left + right*2) / 3;
        if (v[c1] < v[c2])
            right = c2;
        else
            left = c1;
    }
    if (left < right)
        return v[left] < v[right] ? left : right;
    return left;
}
int SearchRot(int v[], int size, int number) {
    int left = 0, right = size-1, mid;
    int pivot = FindPivot(v, size);
    while (left <= right) {
        mid = (left + right) / 2;
        int pos = (mid + pivot) % size;
        if (v[pos] == number)
            return pos;
        else if (v[pos] < number)
            left = mid+1;
        else
            right = mid-1;
    }
    return -1;
}

Simple binary search, with slight change will work.
See the code below.

// Aim is to find a element k in a rotated sorted array.

#include <iostream>

using namespace std;

int findKElement(int find, int array[], int length)
{
   int start = array[0];
   int end = array[length -1];
   int mid = array[length/2];
   int left = 0;
   int right = length - 1;
    
   while (left <= right) {
       int middle = left + (right-left)/2;
       if (array[middle] == find) return middle;
       
       if (array[left] <= array[middle]) {
           if (find >= array[left] && find < array[middle])
               right = middle - 1;
           else
               left = middle + 1;
       }
       else {
           if (find > array[middle] && find <= array[right])
               left = middle + 1;
           else
               right = middle - 1;
       }
   }
   return -1;
}

int main ()
{
    int length;
    cin >> length;
    int array[length];
    int toFind;
    cin >> toFind;
    for (int i = 0; i < length; i++)
        cin >> array[i];
    cout << "index is " << findKElement(toFind, array, length) << endl;
    return 0;
}

Here is the scala solution:

def pivotIndex(input: Array[Int]):Int={
  val pairs=input zip input.tail;
  val pivotPosition=pairs.indexWhere((x: Pair[Int, Int])=>x._1>x._2);
  val validInput=(pivotPosition>==0) && (pivotPosition==pairs.lastIndexWhere((x: Pair[Int, Int])=>x._1>x._2);
   if(validInput) pivotPosition+1 else -1
}

Solution (considers duplicates as well):

One half of the array is normally ordered. It's either the left or the right. Find the normally ordered half and perform binary search on that if X is inside it. Otherwise, search the other half.

Complexity: O(logN) without duplicates, O(n) with all elements duplicates (because we need to search both halves)

CODE:

public int search(int[] array, int n){
    return search(array, n, 0, array[array.length-1]);
}

private int search(int[] array, int n, int left, int right){

    if (left>right)
        return -1;
    int mid = (left+right) / 2;
    
    if (array[mid] == n)
        return mid;
    
        
    //find the normally ordered array and search in it
    if (array[left] < array[mid])
    {
        //left is normally ordered
        if (array[left]<=n && n<=array[mid])
            return search(array, n, left, mid-1);    //search  left
        else
            return search(array, n, mid+1, right); //search right
    }
    else if (array[mid]<array[right]){
        //right is normally ordered
        if (array[mid] <= n && n <= array[right])
            return search(array, n, mid+1, right);
        else
            return search (array, n, left, mid-1);
    }
    else if (array[left]==array[mid]){    //there are duplicates
        if (array[mid]!=array[right])
            return search(array, n, mid+1, right);
        else
        {
            int l = search(array, n, left, mid-1);
            if (l==-1)
                return search(array, n, mid+1, right);
            return l;
        }
    }
    return -1;
    
}

package com.test;

public class Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		int pivot = -1;
		for (int i = 0; i < array.length - 1; i++) {
			if (array[i] < array[i + 1]) {
				continue;
			} else {
				pivot = i;
			}
		}

		System.out.println("pivot: " + pivot);
	}

}

static void binarySearchRotated(int [] A, int i, int l, int x){ // i=0; l=A.length-1;
		if(i>l){
			return;
		}
		int mid=(i+l)/2;
		if(x==A[mid]){
			System.out.print(mid);
			return;
		} else if(A[mid]>=A[l]){
			if(x>=A[i] && x<A[mid]){
				binarySearchRotated(A, i, mid-1, x);
			} else binarySearchRotated(A, mid+1, l, x);
		} else if(A[mid]<=A[l]){
			if(x>A[mid] && x<=A[l]){
				binarySearchRotated(A, mid+1, l, x);
			} 
			else 
				binarySearchRotated(A, i, mid-1, x);
		}
	}

Can someone please comment on this code? It seems to work, but I would like to know how efficient it is...

public static int findIndexK(int k, int[] a) {
		int index = -1;
		int fromLeft = tryFromLeft(k, a);
		if (fromLeft == -1)
			index = tryFromRight(k, a);
		else
			index = fromLeft;
		return index;
	}

	public static int tryFromLeft(int k, int[] a) {
		int res = -1;
		for (int i = 0; i < a.length; i++){
			if (a[i] > k) break;
			if (a[i]==k) return i;
		}
		return res;
	}

	public static int tryFromRight(int k, int[] a) {
		int res = -1;
		for (int i = a.length - 1; i >= 0; i--){
			if (a[i] < k) break;
			if (a[i] == k) return i;
		}
		return res;
	}

	public static void main(String[] args) {
		int[] a = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };
		int k = 0;
		System.out.println(findIndexK(k, a));

}

// 1. L < M < R (1,2,3) - regular QuickSort
// 2. L < M > R (2,5,1)
// 3. L > M < R (5,1,3)
// 4. L > M > R (3,2,1) - reverse QuickSort
static int FindInRotatedArray(int[] a, int k)
{
    int l = 0;
    int r = a.Length - 1;
    while (l < r)
    {
        int m = l + (r - l) / 2;

        if (k == a[m]) return m;

        if (a[l] <= a[m] && a[m] <= a[r]) // 1
        {
            if (a[m] > k) r = m - 1;
            else l = m + 1;
        }
        else if (a[l] <= a[m] && a[m] >= a[r]) // 2
        {
            if (a[l] <= k && k < a[m]) r = m - 1;
            else l = m + 1;
        }
        else if (a[l] >= a[m] && a[m] <= a[r]) // 3
        {
            if (a[m] < k && k <= a[r]) l = m + 1;
            else r = m - 1;
        }
        else // 4
        {
            if (a[m] > k) l = m + 1;
            else r = m - 1;
        }
    }

    return a[l] == k ? l : -1;
}

Time Complexity: O(n)

static void Main(string[] args)
        {

           int[] arr = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };
            Console.WriteLine(PivotIndex(arr));
            Console.ReadLine();

}
static int PivotIndex(int[] arr) {

             int startIndex = 0;
             int endIndex = arr.Length - 1;

             for (int i = 0; i < arr.Length - 1; i++)
             //while()
             {
                 if (arr[startIndex] > arr[endIndex])
                 {
                     startIndex++;
                     endIndex--;
                 }
                 else {
                     return endIndex+1;
                 }

             
             }


             return -1;
         }

public class Tab {

public static int res (int K, int g, int d, int[] tab){
if (tab.length==0){
	return -1;
}
	if (g==d){
    if (K==tab[g]){
        return g;
                  }
        else{
        return (-1);
            }
        }
else{
    int N = (g+d)/2;
    if (tab[N]==K){
        return N;
                  }
        else{
            if (tab[N]<tab[g]){
                              if (K<=tab[d]){
                                  return res(K,N,d,tab);
                              }
                              else{
                                  return res (K,g,N,tab);
                                  }
                              }
               else{
                if (K>=tab[g]){
                                  return res(K,g,N,tab);
                              }
                              else{
                                  return res (K,N,d,tab);
                                  }
               }
            }
    }
}

public static void main (String[] args){
int[] tab = {4,5,6,7,8,9,1,2,3};
System.out.println(res(1,0,tab.length,tab));
}
}

public class kParlindrome {
public boolean check(String s, int threshold)
{
return checkKparlindrome(s, 0, s.length()-1, 0, threshold);
}
public boolean checkKparlindrome(String s, int bpointer, int epointer, int misCnt, int threshold)
{
if(bpointer< 0 || epointer>=s.length())
return false;
if(epointer <= bpointer)
return true;
if(misCnt > threshold)
{
return false;
}
if(s.charAt(bpointer) == s.charAt(epointer))
{
boolean res = checkKparlindrome(s, bpointer+1, epointer-1, misCnt+2,threshold);
if (res)
return res;
else
return false;
}
else
{
//move bpointer
boolean res = checkKparlindrome(s, bpointer+1, epointer, misCnt+1,threshold);
if(res)
return true;
//move epointer
res = checkKparlindrome(s, bpointer, epointer-1, misCnt+1,threshold);
if(res)
return true;
//move
res = checkKparlindrome(s, bpointer+1, epointer-1, misCnt+2,threshold);
if(res)
return true;
return false;
}
}
public static void main(String[] args)
{
kParlindrome kp = new kParlindrome();
System.out.println(kp.check("bacdedafdeafdakljlke",3));
}
}

This code will be ok.

int Search(std::vector<int> & v, int k) {
  int b = 0;
  int e = v.size() - 1;
  while (b <= e) {
    int mid = b + (e - b) / 2;
    if (v[mid] == k) return mid;
    else if (v[mid] > v[e]) {
      if (k > v[e] && k < v[mid]) e = mid - 1;
      else b = mid + 1;
    } else if (v[mid] < v[e]) {
      if (t > v[mid] && t <= v[e]) b = mid + 1;
      else e = mid - 1;
    } else {
      e--;
    }
  }
  return -1;
}

public static int midIndex(int[] arr, int k)
	{
		return minIndex(arr, k, 0, arr.length);
	}
	
	private static int minIndex(int[] arr, int k, int l, int r)
	{
		while(l < r)
		{
			int mid = (r - l) / 2;
			mid += l;
			
			if(arr[mid] == k)
				return mid;
			
			if(arr[l] <= arr[mid])
			{
				if(k >= arr[l] && k < arr[mid])
				{
					r = mid;
				}
				else
				{
					l = mid + 1;
				}
			}
			else
			{
				if(k < arr[mid] && k >= arr[l])
				{
					r = mid;
				}
				else
				{
					l = mid + 1;
				}
				
			}
			
			return minIndex(arr, k, l, r);
		}
		return -1;

}