CodingQuestion/src/LeetCode-35-Search-Insert-Position.java at master · drinkbeer/CodingQuestion · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*
LeetCode: https://leetcode.com/problems/search-insert-position/
LintCode: http://www.lintcode.com/problem/search-insert-position/
JiuZhang: http://www.jiuzhang.com/solutions/search-insert-position/
ProgramCreek: http://www.programcreek.com/2013/01/leetcode-search-insert-position/

Analysis:
Find the first position >= target
*/
public class Solution {
    // Find the first position >= target
    public int searchInsert(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;

        while(lo + 1 < hi){
            int mid = lo + (hi - lo) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) hi = mid;
            else lo = mid;
        }

        // get first position >= target
        if(nums[lo] >= target) return lo;
        else if(nums[hi] >= target) return hi;
        else return hi + 1;
    }

    // Find the first position < target, return +1. Doesn't work!!!!!!
    // public int searchInsert(int[] nums, int target) {
    //     int lo = 0, hi = nums.length - 1;

    //     while(lo + 1 < hi){
    //         int mid = lo + (hi - lo) / 2;
    //         if(nums[mid] == target) return mid;
    //         else if(nums[mid] > target) hi = mid;
    //         else lo = mid;
    //     }

    //     // get first position >= target, should + 1
    //     if(nums[lo] < target) return lo + 1;
    //     else if(nums[hi] < target) return hi + 1;
    //     else return lo + 1;
    // }


    // 1.Brute Force
    // O(N)
    // public int searchInsert(int[] nums, int target) {
    //     int i = 0;
    //     for (; i < nums.length; i++) {
    //         if (nums[i] >= target) return i;
    //     }
    //     return i;
    // }

    // 2.Binary Search. get first position >= target
    public int searchInsert(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;

        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;

            if (nums[mid] == target) hi = mid;
            else if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }

        if (nums[lo] >= target) return lo;
        if (nums[hi] >= target) return hi;
        return hi + 1;
    }

}