搜索插入位置（Java实现）

旧城等待， 2023-07-18 02:30 15阅读 0赞

## 搜索插入位置（Java实现） ##

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。  
你可以假设数组中无重复元素。

示例 1:
    输入: [1,3,5,6], 5
    输出: 2
    
    示例 2:
    输入: [1,3,5,6], 2
    输出: 1
    
    示例 3:
    输入: [1,3,5,6], 7
    输出: 4
    
    示例 4:
    输入: [1,3,5,6], 0
    输出: 0

我的思路很简单，就是先遍历查找，借助数据结构ArrayList，如果找到就返回下标；找不到就add进ArrayList中，然后对ArrayList排序，使用indexOf（target）来返回target的下标即可。  
代码实现之：

package Day49;
    
    import java.util.ArrayList;
    import java.util.Collections;
    
    /** * @Author Zhongger * @Description 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 * 你可以假设数组中无重复元素。 * @Date 2020.3.23 */
    public class SearchInsertSolution { 
        public static void main(String[] args) { 
            int[] nums={ 1,3,5,6};
            int target=7;
            System.out.println(new SearchInsertSolution().searchInsert(nums, target));
        }
        public int searchInsert(int[] nums, int target) { 
            if (nums==null){ 
                return -1;
            }
            if (nums.length<=0){ 
                return -1;
            }
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) { 
                list.add(nums[i]);
                if (target==nums[i]){ 
                    return i;
                }
            }
            list.add(target);
            Collections.sort(list);
            return list.indexOf(target);
        }
    }

还有一种方法就是二分查找法，简单得很：

public int searchInsert2(int[] nums, int target) { 
            int left = 0, right = nums.length - 1;
            while(left <= right) { 
                int mid = (left + right) / 2;
                if(nums[mid] == target) { 
                    return mid;
                } else if(nums[mid] < target) { 
                    left = mid + 1;
                } else { 
                    right = mid - 1;
                }
            }
            return left;
        }