Skip to content

Instantly share code, notes, and snippets.

@goh-chunlin
Last active March 4, 2022 13:58
Show Gist options
  • Save goh-chunlin/bf80067b1a9f676a65bd5206241d8e2e to your computer and use it in GitHub Desktop.
Save goh-chunlin/bf80067b1a9f676a65bd5206241d8e2e to your computer and use it in GitHub Desktop.
Search Insertion Position - Recursion
public int SearchInsert(int[] nums, int target) {
return Search(nums, target, 0, nums.Length - 1);
}
private int Search(int[] nums, int target, int startingIndex, int endingIndex) {
int middleIndex = startingIndex + (endingIndex + 1 - startingIndex) / 2;
if (startingIndex == endingIndex) {
if (target <= nums[startingIndex]) {
return startingIndex;
} else {
return startingIndex + 1;
}
}
else if (endingIndex - startingIndex == 1) {
if (target <= nums[startingIndex]) {
return startingIndex;
} else if (target <= nums[endingIndex]) {
return endingIndex;
} else {
return endingIndex + 1;
}
}
else if (target == nums[middleIndex])
{
return middleIndex;
}
else if (target < nums[middleIndex]) {
return Search(nums, target, startingIndex, middleIndex);
} else {
return Search(nums, target, middleIndex, endingIndex);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment