1.

You are given a sorted array of integers. It is given that each element in the array is unique.

Answer»
You have to find the index where the element is located in the array. If it is not located in the array, you have to return the index at which it should be inserted in the array so that the array remains sorted. You can’t use extra space and the expected time complexity is O(log2N) where N is the number of elements in the array.

Since the array is sorted, we will use Binary Search to find the element. If the element is not found, the index at which we insert an element is always the ceil Index. So, what is the ceil index? At the end of the binary search, ceil index is where the low (or left) pointer points. So, the code for the same is shown below.

Java Code to Search Element/Insert Position

import java.util.*;
class Main {

public static int ceilIndex(int[] nums, int target) {
int lo = 0;
int hi = nums.length-1;

while(lo <= hi) {
int mid = lo + (hi-lo)/2;

if(nums[mid] == target) {
return mid;
} else if(nums[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}

return lo; //ceil
}

public static int search(int[] nums, int target) {
//insert position is actually the ceil of the element
return ceilIndex(nums,target);
}

public static void main(String args[]) {
// Your code goes here
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];

for(int i=0;i<n;i++) {
arr[i] = scn.nextInt();
}

int target = scn.nextInt();

System.out.println(search(arr,target));

}
} 

Sample Output  

When the element is present in the array

Input:
4
1 3 5 6
5

Output: 2

When the element is not present in the array

Input:
4
1 3 5 6
4

Output: 2


  • Time Complexity: The time complexity is O(log2N) where N is the number of elements in the array.


  • Auxiliary Space: O(1) as we have not used any extra space.


Discussion

No Comment Found

Related InterviewSolutions