Leetcode 35. Search insert position

stuff about computer science and programming
Post Reply
Online
User avatar
dendiz
Site Admin
Posts: 234
Joined: Wed Oct 10, 2018 3:48 am

Leetcode 35. Search insert position

Post by dendiz » Wed Jan 16, 2019 8:52 am

Given a sorted array 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.

You may assume no duplicates in the array.
Whenever you see "sorted array" think binary search.

This is a typical binary search problem with an added requirement to return the insertion index.

If you trace a binary search start,end,mid pointers you will see that if the search is not successful the start pointer will be pointing to the insertion location.

Code: Select all

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

Post Reply