SearchInsertPosition [source code]

public class SearchInsertPosition {
static

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        if (nums.length == 0) return -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return lo;
    }
}

    public static void main(String[] args) {
        SearchInsertPosition.Solution tester = new SearchInsertPosition.Solution();
        assert tester.searchInsert(new int[]{1,3,5,6}, 5) == 2;
        assert tester.searchInsert(new int[]{1,3,5,6}, 2) == 1;
        assert tester.searchInsert(new int[]{1,3,5,6}, 7) == 4;
        assert tester.searchInsert(new int[]{1,3,5,6}, 0) == 0;
        System.out.println(tester.searchInsert(new int[]{1}, Integer.parseInt(args[0])));
    }
}

Binary Search 的每一个细节都要掌握, 比如 premature exit 用的是 return 而不是break; default return 用来返回not found; header里面可以取等号, 等等;

return lo 这个是在标准代码上的一个小改动, 这样在 not found 的情况下可以找到 insert 的位置;

最后的速度是6(31), 倒是不太理想;
看了一下, 那些稍微快一点的基本代码也都差不多;
discussion最优解基本是这个一模一样的写法;

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.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Difficulty:Easy
Category:Algorithms
Acceptance:39.57%
Contributor: LeetCode
Related Topics
array binary search
Similar Questions
First Bad Version