Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created November 23, 2017 19:14
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/42a6a5be30fb39c89f9ed169e57d485e to your computer and use it in GitHub Desktop.
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.
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