Created
November 24, 2017 01:12
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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