CC-12 : Find insert position of number in a sorted array.

Description:

Given a sorted input array and an element to be inserted, search the index of where element needs to be inserted so that sort order is maintained.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 3, 22, 44, 77, 77, 77, 122, 144, 201,	Insert position of 88 is 6 Insert position of 55 is 3 Insert position of 2 is 0 Insert position of 202 is 9 Insert position of 44 is 2

Pseudocode:

findInsertPos(nums[], tosearch):

Integer array named nums and integer named toSearch to be searched are received as input parameters.

Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.

Set integer variable lastIdx to nums.length-1, we will use this variable to check the last index of partition in which are searching for required integer.

Set integer variable insIdx to -1, we will use this variable to store the position at which toSearch can be inserted in nums.

While (firstIdx <= lastIdx) do the following steps:

Set integer variable midCount to (lastIdx-firstIdx)/2.

Set integer variable midIdx to (firstIdx+midCount)to get mid index of current partition. We will use midIdx to partition the array into 2 parts.

If (nums[midIdx]==toSearch) :

Set numIdx to midIdx; this means have found the required element.

Set lastIdx to midIdx-1.

Else if nums[midIdx] > toSearch then:

Set lastIdx=(midIdx-1) as we need to search in lower partition now.

Else:

Set firstIdx=midIdx+1, as we need to search in the higher partition now.

Return insIdx as it contains the position at which toSearch can be inserted in nums.

Code:

public int findInsertPos(int[] nums, int toSearch){
	int firstIdx=0;
	int lastIdx=nums.length-1;
	int insIdx=nums.length;
	while (firstIdx <= lastIdx) {
		int midIdx=(lastIdx+firstIdx)/2;
		if (nums[midIdx]>=toSearch) {
			insIdx=midIdx;
			lastIdx=midIdx-1;
		} else {
			firstIdx=midIdx+1;
		}			
	}	
	return insIdx;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SearchFindInsertPosition {

public int findInsertPos(int[] nums, int toSearch){
	int firstIdx=0;
	int lastIdx=nums.length-1;
	int insIdx=nums.length;
	while (firstIdx <= lastIdx) {
		int midIdx=(lastIdx+firstIdx)/2;
		if (nums[midIdx]>=toSearch) {
			insIdx=midIdx;
			lastIdx=midIdx-1;
		} else {
			firstIdx=midIdx+1;
		}			
	}	
	return insIdx;
}


public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	
	SearchFindInsertPosition search=new SearchFindInsertPosition();
	int[] nums= { 3,22,44,77,77,77,122, 144, 201};
	
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	
	int toInsert=88;
	retVal=search.findInsertPos(nums, toInsert);
	System.out.println("\n\nInsert position of "+ toInsert + " is " + retVal);	
	
	
	toInsert=55;
	retVal=search.findInsertPos(nums, toInsert);
	System.out.println("\n\nInsert position of "+ toInsert + " is " + retVal);	
	
	
	toInsert=2;
	retVal=search.findInsertPos(nums, toInsert);
	System.out.println("\n\nInsert position of "+ toInsert + " is " + retVal);	
	
	
	toInsert=202;
	retVal=search.findInsertPos(nums, toInsert);
	System.out.println("\n\nInsert position of "+ toInsert + " is " + retVal);	
	
	toInsert=44;
	retVal=search.findInsertPos(nums, toInsert);
	System.out.println("\n\nInsert position of "+ toInsert + " is " + retVal);	
	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}