ARTS leetcode9 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:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0
           

這道題目的意思是，給了一個排好序的數組和一個目标值，将目标值插入到數組中，如果找到了該目标則傳回該索引，否則傳回這個元素應該在哪裡插入。

思路：

（1）這個數組有值不為空

（2）分情況，值在數組中存在和不存在；不存在的時候，且大于數組最大值，則傳回的索引為數組的長度；如果小于數組的最小值，則傳回0

（3）存在于數組中的時候，如果該值大于等于目标值，那麼就将該索引直接傳回，跳出循環break。

class Solution {
    public int searchInsert(int[] nums, int target) {
         int index = 0;
        if(nums != null && nums.length > 0){
            int len = nums.length;
            if(Arrays.binarySearch(nums,target) <= 0 && target > nums[len-1]){
                index = len;
            }
            for(int i=0;i<len;i++){
                if((nums[i] == target)||(nums[i]>target)){
                    index = i;
                    break;
                }
            }
        }
        return  index;
    }
}
           

Runtime: 0 ms, faster than 100.00% of Java online submissions for Search Insert Position.
Memory Usage: 39.6 MB, less than 6.42% of Java online submissions for Search Insert Position.
           

别人的解答，采用二分法，時間複雜度O(nLogN),代碼如下：

思路：分别處理數組為空，target大于數組最大值和小于數組最小值的情況，然後使用二分法查找該元素在有序數組中的位置。

if(nums.length == 0) return 0;
    if(target <= nums[0]) return 0;
    if(target > nums[nums.length-1]) return nums.length;
    
    int low = 0;
    int high = nums.length-1;
    int mid = (low+high)/2;
    
    while(low != mid) {
        if(target == nums[mid]) return mid;
        if(target < nums[mid]) high = mid;
        else low = mid;
        mid = (low+high)/2;
    }
    return high;