Question

How to search insert position of K in a sorted list with Java

Answer 1

// Given a sorted array/vector/list of distinct integers and a target value K, 
// return the index if the target is found. 
// If not, return the index where it would be if it were inserted in order.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SearchInsertPosition {

    // Function to find the index of k or the position where it should be inserted
    public static int searchInsertPositionOfK(List<Integer> list, int k) {
        for (int i = 0; i < list.size(); i++) {
            // If k is found or needs to be inserted before list.get(i)
            if (list.get(i) >= k) {
                return i;
            }
        }
        // If k is greater than all elements, it should be inserted at the end
        return list.size();
    }

    public static void main(String[] args) {
        List<Integer> list1 = Arrays.asList(1, 3, 5, 6, 7, 8);
        int k1 = 5;
        System.out.println(searchInsertPositionOfK(list1, k1));

        List<Integer> list2 = Arrays.asList(1, 3, 5, 6, 7, 8);
        int k2 = 2;
        System.out.println(searchInsertPositionOfK(list2, k2));

        List<Integer> list3 = Arrays.asList(1, 3, 5, 6, 7, 8);
        int k3 = 9;
        System.out.println(searchInsertPositionOfK(list3, k3));
    }
}



/*
run:

2
1
6

*/

 

Learn SQL from A to Z at LearnSQL.com

Answer 2

// Given a sorted array/vector/list of distinct integers and a target value K, 
// return the index if the target is found. 
// If not, return the index where it would be if it were inserted in order.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SearchInsertPosition {

    // Function to find the index of k or the position where it should be inserted - Using Binary Search
    public static int searchInsertPositionOfK(List<Integer> list, int k) {
        int left = 0, right = list.size() - 1;  
 
        while (left <= right) {  
     
            int mid = left + (right - left) / 2;  
     
            if (list.get(mid) == k) {  
                return mid;  
            }  
     
            // If k is smaller, search in the left half
            else if (list.get(mid) > k) {
                right = mid - 1;  
            }  
     
            // If k is larger, search in the right half
            else {  
                left = mid + 1;  
            }  
        }  
     
        // If k is not found, it should be inserted at the end
        return left;  
    }

    public static void main(String[] args) {
        List<Integer> list1 = Arrays.asList(1, 3, 5, 6, 7, 8);
        int k1 = 5;
        System.out.println(searchInsertPositionOfK(list1, k1));

        List<Integer> list2 = Arrays.asList(1, 3, 5, 6, 7, 8);
        int k2 = 2;
        System.out.println(searchInsertPositionOfK(list2, k2));

        List<Integer> list3 = Arrays.asList(1, 3, 5, 6, 7, 8);
        int k3 = 9;
        System.out.println(searchInsertPositionOfK(list3, k3));
    }
}



/*
run:

2
1
6

*/

 

Learn SQL from A to Z at LearnSQL.com