Created
December 15, 2017 19:00
-
-
Save jianminchen/44820cbb21735bc9016e135f3581a731 to your computer and use it in GitHub Desktop.
Array value equal index - code review - need to fix the time complexity and space complexity, to lower to O(logn) for time, and O(1) for space.
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 | |
{ | |
/// <summary> | |
/// code review on Dec. 15, 2017 | |
/// </summary> | |
/// <param name="arr"></param> | |
/// <returns></returns> | |
public static int IndexEqualsValueSearch(int[] arr) // [0, 1, 2, 3] | |
{ | |
if (arr == null || arr.Length == 0) // false | |
{ | |
return -1; | |
} | |
var length = arr.Length; // 4 | |
return binarySearch(arr, 0, length - 1); // 0, 0 , 3 | |
} | |
/// <summary> | |
/// time complexity is O(n), space complexity is O(1) | |
/// </summary> | |
/// <param name="numbers"></param> | |
/// <param name="start"></param> | |
/// <param name="end"></param> | |
/// <returns></returns> | |
private static int binarySearch(int[] numbers, int start, int end) // logn - | |
{ | |
if (start > end) // false | |
{ | |
return -1; | |
} | |
var middle = start + (end - start) / 2; // 1 | |
var middleValue = numbers[middle]; // 0 | |
// base case | |
if (middleValue == middle) // | |
{ | |
// You need to make some changes here | |
// You definitely know 1 index | |
// [0 0 0 0 0] | |
// middle = 2 | |
// [0 0] | |
if (middle > 0 && numbers[middle - 1] == (middle -1)) | |
{ | |
return binarySearch(numbers, start, middle - 1); | |
} | |
else | |
{ | |
return middle; // 1 -> lowest one - bug fix | |
} | |
} | |
else if (middleValue < middle) | |
{ | |
start = middle + 1; | |
} | |
else | |
{ | |
end = middle - 1; | |
} | |
return binarySearch(numbers, start, end); | |
} | |
static void Main(string[] args) | |
{ | |
} | |
} | |
// [-8, 0, 2, 5] - distinct ascending -> increment at least 1 | |
// [0, 1, 2, 3] -> ascending order -> increment 1 | |
// arr[i] - i -> array not descending | |
// arr[i] <= arr[i] if i < j | |
// [0, 1, 2, 3] | |
// newArray = arr[i] - i , saying that this array is sorted, | |
// [0,0,0,0] -> sorted, | |
// argument if it is sorted, binary search | |
// O(logn) given value 0, find index - arr[i] - i = 0, | |
// space O(1) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment