Search Insertion Position

Given a sorted array of distinct integers and a target value, how could we get the index of the target is found? In addition, if the target is not found, we need to return the index where it would be if it were inserted in order.

The first solution came to my mind is a recursive one. Oh my…

Source code: https://gist.github.com/goh-chunlin/bf80067b1a9f676a65bd5206241d8e2e

We can further reduce the number of base cases to make our recursion code shorter, as demonstrated below.

Source code: https://gist.github.com/goh-chunlin/3c7defc425ccd123800878ff7b299b06

Based on this, we can change it to be iterative as follows.

Source code: https://gist.github.com/goh-chunlin/850e59513693e56e36107d25f487d5f0