Skip to content

Instantly share code, notes, and snippets.

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/1fc27d24779605cf23a08d5bd05bee37 to your computer and use it in GitHub Desktop.
Save jianminchen/1fc27d24779605cf23a08d5bd05bee37 to your computer and use it in GitHub Desktop.
Leetcode 33 - search sorted rotated array - discussion two ranges - inclusive, exclusive two cases - code is more clear to follow
using System;
class Solution
{
public static int ShiftedArrSearch(int[] shiftArr, int num)
{
if (shiftArr == null || shiftArr.Length == 0)
{
return -1;
}
return runModifiedBinarySearch(shiftArr, num, 0, shiftArr.Length - 1);
}
/// <summary>
/// code review on Nov. 23, 2017
/// Make sure that the code is simple as possible.
/// No code smell, no copy and paste.
/// ONLY CHECK THE FIRST HALF AND SEE IF IT IS IN THE FIRST HALF.
/// </summary>
/// <param name="numbers"></param>
/// <param name="search"></param>
/// <param name="start"></param>
/// <param name="end"></param>
/// <returns></returns>
private static int runModifiedBinarySearch(int[] numbers, int search, int start, int end)
{
if (start > end)
{
return -1;
}
int middle = start + (end - start) / 2;
bool found = numbers[middle] == search;
// base case, find one solution.
if (found)
{
return middle;
}
var middleValue = numbers[middle];
var startValue = numbers[start];
var endValue = numbers[end];
var firstHalfAscending = startValue <= middleValue; // the first half can be only one node
var notSmallerThanStartValue = search >= startValue;
var smallerThanMiddleValue = search < middleValue;
var oneRangeChecking = notSmallerThanStartValue && smallerThanMiddleValue; // inclusive
var twoRangesChecking = notSmallerThanStartValue || smallerThanMiddleValue; // exclusive
var firstHalfAscendingChecked = firstHalfAscending && oneRangeChecking;
var fistHalfNotAscendingChecked = !firstHalfAscending && twoRangesChecking;
if (firstHalfAscendingChecked || fistHalfNotAscendingChecked)
{
return runModifiedBinarySearch(numbers, search, start, middle - 1);
}
else
{
return runModifiedBinarySearch(numbers, search, middle + 1, end);
}
}
static void Main(string[] args)
{
RunTestcase();
}
public static void RunTestcase()
{
ShiftedArrSearch(new int[] { 1, 3 }, 3);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment