Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created February 5, 2018 07:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/473e690328b7fbf81e39b1f4497711cd to your computer and use it in GitHub Desktop.
Save jianminchen/473e690328b7fbf81e39b1f4497711cd to your computer and use it in GitHub Desktop.
Find index given value shifted array search - code review
using System;
//if lo >mid -> pivot is on the right
// if hi <mid -> pivot is on the left;
//Case 1 :- pivot on right hi < mid -> and lo <num <mid :- hi = mid-1;
//case 2 :- else of case 1 :- lo = mid +1
//case 3 :- pivot on left end :- lo > mid :- and mid < num < hi :- lo = mid+1
//case 4 :- else of case 1 :- hi= mid-1;
// [1,2] :- 2
// mid - a[0] -> 1
class Solution
{
public static int ShiftedArrSearch(int[] shiftArr, int num)
{
// your code goes here
if(shiftArr ==null || shiftArr.Length==0)
return -1;
int lo=0, hi= shiftArr.Length-1;
while(lo<=hi)
{
int mid = lo + (hi-lo)/2;
int middleValue = shiftArr[mid];
int highValue = shiftArr[hi];
if(middleValue == num)
return mid;
if(highValue < middleValue) //case 1 and 2 ?
{
// left half ascending
if(shiftArr[lo] <= num && middleValue > num)
hi=mid-1;
else
lo= mid +1;
}
else
{
if(shiftArr[hi] >= num && middleValue < num)
lo=mid+1;
else
hi=mid-1;
}
}
return -1;
}
static void Main(string[] args)
{
int[] arr = new int[]{1,2};
Console.WriteLine(ShiftedArrSearch(arr, 2));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment