当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.035.Search Insert Position

LeetCode.035.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

解题过程

经典的二分搜索,没啥说的,如果要搜索的值不再数组中,最后肯定以high+1==low结束

package _035_SearchInsertPosition;

class Solution {
    public int searchInsert(int[] nums, int target) {
        if(nums.length==0)
            return 0;
        int low = 0;
        int high = nums.length-1;
        while(low<=high){
            int mid = (low+high)/2;
            if(target==nums[mid]){
                return mid;
            }else if(target>nums[mid]){
                low = mid+1;
            }else{
                high = mid-1;
            }
        }
        return high+1;//最后high+1肯定等于low
    }
}

public class SearchInsertPosition {
    public static void main(String[] args){
        Solution solution = new Solution();
        int[] input = {1};
        System.out.println(solution.searchInsert(input, 1));
    }
}

GitHub代码


上一篇 Spring-基础注解

下一篇 LeetCode.028.Implement strStr()

阅读
234
阅读预计1分钟
创建日期 2018-02-25
修改日期 2018-02-26
类别
百度推荐