Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created February 3, 2018 19:07
Show Gist options
  • Save jianminchen/8edba016136ad5f06289648396cab750 to your computer and use it in GitHub Desktop.
Save jianminchen/8edba016136ad5f06289648396cab750 to your computer and use it in GitHub Desktop.
Shifted Array search - study code written by Java code
import java.io.*;
import java.util.*;
class Solution {
static int shiftedArrSearch(int[] shiftArr, int num) {
// your code goes here
/*
[9, 12, 17, 2, 4, 5], num = 1, return -1
Brute force : O(N)
binary search : O(log(N))
getMin() : log(N)
log(N)
*/
int minIndex = getMin(shiftArr);
int elemInLeft = -1;
int elemInRight = -1;
if (minIndex != 0){
elemInLeft = Arrays.binarySearch(shiftArr, 0, minIndex, num);
}
elemInRight = Arrays.binarySearch(shiftArr, minIndex, shiftArr.length, num);
int res = -1;
if (elemInLeft != -1)
return elemInLeft;
else if (elemInRight != -1)
return elemInRight;
return res;
}
static int getMin(int[] arr) {
int resInd = 0;
int lo = 0;
int high = arr.length-1;
while (lo <= high) {
int mid = lo + (high - lo)/2;
if (mid == 0 || arr[mid] < arr[mid-1]) {
return mid;
}
else if (arr[mid] < arr[high])
{
high = mid - 1;
}
else
{
lo = mid + 1;
}
}
return resInd;
}
public static void main(String[] args) {
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment