Created
November 23, 2017 19:44
-
-
Save jianminchen/e938cbcdbdad25bce33f42bc5cb87f0a to your computer and use it in GitHub Desktop.
Binary search - first half range boundary check
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 startBoundaryChecked = search >= startValue; | |
var middleBoundaryChecked = search < middleValue; | |
var firstHalfTwoBoundariesChecked = startBoundaryChecked && middleBoundaryChecked; | |
if (firstHalfTwoBoundariesChecked) | |
{ | |
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, 2 }, 2); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment