LintCode 60. Search Insert Position 原创Java参考解答

LintCode 60. Search Insert Position 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/search-insert-position/

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.

Example

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

解题思路

  1. 先检查数组nums是否为null或者为空数组,若是则直接返回0。
  2. 用二分法在数组中查找target值的位置。若查到了,直接返回该target位置。如果没有查到,则比较二分法查找后最后剩下两个位置的数与target值的大小关系。放在相应位置即可。

参考代码

public class Solution { 
    /**  
     * param A : an integer sorted array 
     * param target :  an integer to be inserted 
     * return : an integer 
     */ 
    public int searchInsert(int[] A, int target) { 
        if (A == null || A.length == 0) { 
            return 0; 
        } 
         
        int start = 0; 
        int end = A.length - 1; 
        while (start + 1 < end) { 
            int mid = start + (end - start) / 2; 
            if (A[mid] == target) { 
                return mid; 
            } else if (A[mid] < target) { 
                start = mid; 
            } else { 
                end = mid; 
            } 
        } 
         
 
        if (A[end] < target) { 
            return end + 1; 
        } else if (A[start] < target) { 
            return end; 
        } else { 
            return start; 
        }          
    } 
}

相关题目

LintCode All in One 原创题目讲解汇总

发表评论

您的电子邮箱地址不会被公开。