Solving the 'Search Insert Position' Puzzle in C

Introduction

In this short post, we'll go over a simple way to tackle the 'Search Insert Position' problem in C.

Feel free to follow along with me, and give the problem a try yourself!

Problem Statement

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.

Requirements:

• O (log n) time complexity

Note how as the size of the problem increases, the rate of change decreases.

Process

The best way to approach these types of problems is to break them down into simpler pieces--this can be done using comments.

My first thought was binary search, since its an efficient way to search for a specific value in a pre-sorted list.

Also, it just so happens to have the time complexity we're looking for.

int searchInsert(int* nums, int numsSize, int target)
{
	// Binary Search

	// find the middle index
	// if target is greater than middle value, search right half
	// if target is less than middle value, search left half
	// else (if target equals middle value), return middle index
	// finally, return the left-most index in the array
}

With a basic outline, we can start coding.

int searchInsert(int* nums, int numsSize, int target)
{
	// Binary Search

	int l = 0;
	int r = numsSize-1;

	while (l<=r)
	{
		// find the middle index
		int mid = (l+r)/2;

		// if target is less than middle value, search left half
		if (target < nums[mid])
			r = mid-1;
		// if target is greater than middle value, search right half
		else if (target > nums[mid])
			l = mid+1;
		// else (if target equals middle value), return middle index
		else
			return mid;
	}

	// finally, return the left-most index in the array
}

So we now have an implementation of binary search, but you'll notice that the last comment is missing code.

Recall that we need to not only find the target, but return where it will go if it's not in the array.

Thus, after we keep whittling down the list by half each time, the while loop eventually terminates when either no mid is found or just after there is one element in the list. At this point, either the target is found, r changes value, or l changes value.

We can simply return l at the end because if the target is greater than the one number left, we should return that index plus one. If the target is less, it should replace, and thus, return the current index (so l doesn't change).

So the final code stands as:

int searchInsert(int* nums, int numsSize, int target)
{
	// Binary Search

	int l = 0;
	int r = numsSize-1;

	while (l<=r)
	{
		// find the middle index
		int mid = (l+r)/2;

		// if target is less than middle value, search left half
		if (target < nums[mid])
			r = mid-1;
		// if target is greater than middle value, search right half
		else if (target > nums[mid])
			l = mid+1;
		// else (if target equals middle value), return middle index
		else
			return mid;
	}

	// finally, return the left-most index in the array
	return l;
}

Final Thoughts

Hopefully this explanation was useful, and you were able to try the puzzle out yourself. Thanks for reading!