Code Destine

Problem Statement

You have given a sorted array and a target value, write a program to search the target value in the sorted array. If the target value is found, then return its index otherwise return the index where it would be present if it is inserted in the sorted array.

Note: Array contains no duplicates.

Example 

Input :- [1, 2, 3, 6, 7, 10], target= 3
Output :- 2

Input :- [1, 2, 3, 6, 7, 10], target= 5
Output :- 3

Input :- [1, 2, 3, 6, 7, 10], target= 9
Output :- 5

Solution

This problem can be solved using a linear search and a modified version of the binary search algorithm. The time complexity of a linear search algorithm is O(N) and of binary search algorithm is O(logN), where N is the size of the array.

Linear Search – O(N)

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		int result = main.searchInsert(new int[] {1, 2, 3, 6, 7, 10}, 9);
		System.out.println(result);
	}

	public int searchInsert(int[] nums, int target) {       
        int i;
        for(i=0; i<nums.length; i++){            
            if(target == nums[i]){
                return i;
            }else if(target < nums[i]){
                return i;
            }
        }
        return i;
    }
}

Binary Search – O(logN)

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		int result = main.searchInsert(new int[] {1, 2, 3, 6, 7, 10}, 9);
		System.out.println(result);
	}

	public int searchInsert(int[] nums, int target) {        
        
        int start = 0, end = nums.length-1, mid;
        while(start<end){
            
            mid = start + (end-start)/2;
            
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                start = mid+1;
            }else {
                end = mid;
            }            
        }
        
        if(start == nums.length-1 && nums[start] < target){
            return start + 1;
        }else {
            return start;
        }
    }
}

Result

5

That’s all for Search Insert Position in Java, If you liked it, please share your thoughts in a comments section and share it with others too.