LeetCode:35.Search Insert Position

Posted on In

Problem Description

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.

Analysis

  1. Going through the array
  2. Try to find an index i where nums[i] == target and return the i
  3. If step 2 failed, try to find an index i where nums[i] > target. Notieced that the array is sorted and if we have to insert a digit before nums[i], the index of the digit should be i as well, then we have to break from the loop, otherwise the position will be wrong
  4. There is a possibility that the target is bigger than the biggest one in the array, then the index to insert should be the value of nums.length.

Right Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 public int searchInsert(int[] nums, int target) {
    int res = 0;

    for (int i = 0; i < nums.length; i++)
    {
        if(nums[i] == target || nums[i] > target){
            res = i;
            break;
        }else{
            res = nums.length;
        }
    }
    return res;
}