LeetCode #35: Search Insert Position — Solved in Java

Linear Scan and Binary Search

Image Source

LeetCode problem 35, Search Insert Position, asks for the index where a target value should appear in a sorted array. If the value already exists, the method returns that index. If not, it returns the position where the value would go to keep the array sorted. The input array contains distinct integers arranged in ascending order, and the goal is to handle both outcomes within a single return value.

Thinking through this problem in Java starts with paying attention to how comparisons move through sorted data. The idea is to locate a point in the array that meets the search condition, not just find a value that matches. The thought process involves watching how the current element compares with the target, deciding when to stop, and returning the index that fits is what LeetCode test is looking for.

LeetCode: Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Constraints:

• 1 <= nums.length <= 10^4

• -10^4 <= nums[i] <= 10^4

• nums contains distinct values sorted in ascending order.

• -10^4 <= target <= 10^4

Solution 1: Linear Scan Through The Sorted Array

Linear scanning keeps the story very direct. You walk through nums from left to right and look at each value until reaching one that is greater than or equal to target. At that first position, either target already lives there or that spot is exactly where it should be inserted to keep the array sorted.