Previous:

August 20, 2023

example java arrays interviewingSearch Insert Position is a Leetcode problem that presents this question:

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 could do this with a `for`

loop:

```
for (int i = 0; i < nums.length; i++) {
int value = nums[i];
if(value >= target){
return i;
}
}
return nums.length;
```

However, Leetcode has this additional requirement:

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

This mirrors the way an interviewer might ask if you could improve on your solution.

Since the array is sorted, you can use binary search to find the index.

You might get “clever” and use the built-in `Arrays.binarySearch()`

function:

```
int index = Arrays.binarySearch(nums, target);
if(index >= 0) {
return index;
} else{
return -index - 1;
}
```

This shows familiarity with the language, but chances are your interviewer would follow this up by asking you to write out the logic yourself.

```
class Solution {
public int searchInsert(int[] nums, int target) {
int leftIndex = 0;
int rightIndex = nums.length - 1;
while (leftIndex <= rightIndex) {
int centerIndex = (leftIndex + rightIndex) / 2;
int value = nums[centerIndex];
if (target == value) {
return centerIndex;
} else if (target < value) {
rightIndex = centerIndex - 1;
} else if (target > value) {
leftIndex = centerIndex + 1;
}
}
return leftIndex;
}
}
```

Binary search is one of the most popular algorithms, so make sure it’s in your back pocket for problems like this.

Previous:

I posted a new code along for the Search Insert Position Leetcode problem.

Check it out here:

Return the index of an item, even if it's not in the array.

Happy Coding is a community of folks just like you learning about coding.

Do you have a comment or question? Post it here!

Comments are powered by the Happy Coding forum. This page has a corresponding forum post, and replies to that post show up as comments here. Click the button above to go to the forum to post a comment!