CareerCup

public static int newBinarySearch(int A[], int key) {
int L = 0;
int R = A.length - 1;

while (L <= R) {
// Avoid overflow, same as M=(L+R)/2
int M = L + ((R - L) / 2);
System.out.println("L: "+L+" M: "+M+" R: "+R);
if (A[M] == key) return M;

// the bottom half is sorted
if (A[L] <= A[M]) {
if (A[L] <= key && key < A[M])
R = M - 1;
else
L = M + 1;
}
// the upper half is sorted
else {
if (A[M] < key && key <= A[R])
L = M + 1;
else
R = M - 1;
}
}
return -1;
}

I think the questions is: find i, the number of times the array is rotated.

for e.g:

original array: 1 2 3 4 5
rotated array: 4 5 1 2 3
so, i = 2

original array: 5 4 3 2 1
rotated array: 1 5 4 3 2
so, i = 1

The catch is, you do not know beforehand whether the original array is ascending or descending.

I think the question is given a sorted array that is rotated i number of times, perform a modified binary search algorithm on it so that the complexity is still O (log N).

Let's take this case.

original array: 1 2 3 4 5 6 7
rotated array: 4 5 6 7 1 2 3

I think this is how it works.
Given 4 5 6 7 1 2 3

Say that you're looking for 5.
first element: 4.
mid element: 7.
last element: 3.

from this data, you know whether to modify your first or last pointer. There are quite a few cases to this problem. Depending on the data you have above, make the appropriate modification.

khoa give the solution man, you are just complicating the problem

Given 4 5 6 7 1 2 3

first element: 4.
mid element: 7.
last element: 3.

We need to determine which part to search.
Consider there are two arrays:
4 5 6 7 and 7 1 2 3

If we are looking for 6, we know it falls under the first half. We know this by looking at the first and last element of each array.

Ok, its like binary search. To find i, number of rotations, you have to find the position of the smallest element.

start with first and last (low and high). Also look at mid (always low+high/2). if mid is larger than low, then low=mid. If mid is smaller than high, then high-mid. Once u find smallest number, its index-1 is i. then just find array[(i+k)%n] to find kth element.

suppose original: 123456789
rotated 6 times: 456789123
low=1 high=9 mid=5
arr[low]=4 arr[high]=3 arr[mid]=8
therefore, low=5 high=9 mid=7
arr[low]=8 arr[high]=3 arr[mid]=1
therefor, high=7
soon we shall fine we cannot get a smaller number.

i think this would work

the binary search approach can fail in case of even sized array.

Consider this 38, 40, 55, 89, 13, 20, 23, 26

using System;

public class InterviewQuestions
{
//
// Find smallest number (index) in rotated
// sorted array. For example:
// - 1, 3, 5, 6, 7, 1 the answer is 1.
// - 6, 6, 3, 4, 4, 5, 5 the answer is 3.
//
public static int FindSmallest(
int[] numbers
)
{
//
// Implement the function here.
//
throw new NotImplementedException();
}


//
// Find the winner in the circle of N (nPlayers)
// players skipping M (nSkip) and removing Mth
// player. The winner is the last one left.
//
public static int FindWinner(
int nPlayers,
int nSkip
)
{
//
// Implement the function here.
//
throw new NotImplementedException();
}
}

Try out this code

struct Node
{
int data;
Node next;
}CListplayers;

//
// Find the winner in the circle of N (nPlayers)
// players skipping M (nSkip) and removing Mth
// player. The winner is the last one left.
//
public static int FindWinner(
int nPlayers,
int nSkip
)
{
//
// Assume that there is a circular link list CListplayers of N players as declared above
//

int pos=1;
while(true)
{
//Check if this is the node to be delete
if((pos+1 % nskip)==0)
{
//if next node is same node that is only one node is left then this node is the winner
if(node->Next == node)
return node.data;
else
node->Next = node->Next-->Next;
pos=1;
}
node = node->next;
pos++;
}
}
}

You must make an assumption that no repeated elements exist. Otherwise, log(N) search is impossible.

In Java, double elements aren't allowed:

int mid = from + (to - from) / 2;

int fromVal = array[from];
int toVal = array[to - 1];
int midVal = array[mid];

if (elem == midVal)
return mid;

if (midVal > fromVal) {
if (elem >= fromVal && elem < midVal) {
to = mid;
} else {
from = mid + 1;
}
}

if (midVal < fromVal) {
if (elem <= toVal && elem > midVal) {
from = mid + 1;
} else {
to = mid;
}
}

int search(int *array,int low,int high,int key)
{
if(low == high)
{
if(array[low] == key)
return low;
else
return -1;
}

int mid = (low+high)/2;

if(key > array[mid])
{
if(key <= array[high])
return search(array,mid+1,high,key);
else
return search(array,low,mid-1,key);
}
else if(key < array[mid])
{
if(key >= array[low])
return search(array,low,mid-1,key);
else
return search(array,mid+1,high,key);
}
else
return mid;
}

l = length of array
int pos;
if (n > l/2)
   pos = n;
else
   pos = l-n;

bool found = binarysearch(0, pos);
if(!found)
    found = binarysearch(pos, l);

binary search is O(lgn)

public static int getRotations(int[] a)
    {
        if (a.length == 1)
            return 0;
        int start = 0, end = a.length - 1, mid = (start + end) / 2;
        mid = (a.length % 2 == 0) ? (mid + 1) : mid;
        for (int i = 0; i < a.length; i++)
        {
            if (a[mid] >= a[start] && a[start] <= a[start+1])
                start = mid;
            else if (a[mid] <= a[end] && a[start] <= a[start+1])
                end = mid;
            else
                return (a.length - 1 - start);
            mid = (start + end) / 2;
        }
        return 0;

}

int find_element(int a[], int start, int end, int element){

        int mid = start +(end-start)/2;

        if(a[mid] == element)
            return mid;

        if(a[mid] < a[end]){  // Case 3
          /*
             If key is greater than mid but less than end
             look in right part
          /*
          if(element > a[mid] && element <= a[end]){
           return find_element(a,mid+1,end, element);
          }
          /*
             If element is greater than end, we need to look
             in left part
          */
          else if (element > a[end]){
            return find_element(a, start, mid-1,element);
          }
        }
        /*Case where we are in left part of the rotation */
        else if(a[mid] > a[start]){ // Case 2
         /*
             If key is less than mid  and greater than start
             look in left part
          /*
             if(element < a[mid] && element >= a[start]  ){
                 return find_element(a,start,mid-1, element);
             }
             else 
                return find_element(a,mid+1,end, element); 
        }
}

but the array can be either in ascending order or descending before rotation... above code only provide solution for arrays which were in ascending order

#include <stdio.h>
#define NULL -1

int binarySearch(int *, int, int, int);
int rotatedSearch(int *, int, int, int);

int main() {
    int a[3] = {1, 2, 3};
    printf("%d\n",rotatedSearch(a, 1, 0, 2));
    return 0;
}

int rotatedSearch(int *a, int num, int low, int high) {
    int mid = (low + high)/2;
    if (a[mid] == num) return mid;
    if (a[low] < a[mid]){   //Left half is sorted
        if (num >= a[low] && num <= a[mid]) return binarySearch(a, num, low, mid);
        else return rotatedSearch(a, num, mid + 1, high);
    }
    if (a[mid] < a[high]) { //Right half is sorted.
        if (num >= a[mid] && num <= a[high]) return binarySearch(a, num, mid, high);
        else return rotatedSearch(a, num, low, mid - 1);
    }
    return NULL;
}

int binarySearch (int *a, int num, int low, int high) {
    /*When we search in the left half of the array we include a[mid-1]
    /*When we search in the right half we start from a[mid+1].*/
    if (low > high) return NULL;
    int mid = (low + high)/2;
    if (a[mid] == num) return mid;
    else if (num < a[mid]) {
        binarySearch(a, num, low, mid - 1);
    }
    else {
        binarySearch(a, num, mid + 1, high);
    }
}

If Array has unique elements, then log n algorithm is possible
But If Array has many duplicates, then log n is not guaranteed; and can potentially leads to O(n)