Created
November 23, 2017 19:14
-
-
Save jianminchen/42a6a5be30fb39c89f9ed169e57d485e to your computer and use it in GitHub Desktop.
Binary search - Make the code simple as possible, remove code smell, copy/ paste, reduce 4 recursive calls to 2 recursive calls. Structure is more simple.
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; | |
// If the first half is in ascending order, then | |
// the search number is checked to see if it is in the range. | |
var isInFirstHalfWhenAscending = firstHalfAscending && search >= startValue && search < middleValue; | |
// If the first half is not in ascending order, then | |
// the search number is checked to see if it is not in the second half's range. | |
var isNotSecondHalfWhenNotAscending = !firstHalfAscending && (search >= startValue && search < middleValue); | |
var isInFirstHalf = isInFirstHalfWhenAscending || isNotSecondHalfWhenNotAscending; | |
if (isInFirstHalf) | |
{ | |
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