35 Search Insert Position

---

title: Search Insert Position
tags:
- search-insert-position
- No.35
- simple
- binary-search
- divide-conquer

---

Problem

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

Corner Cases

• empty array
• one-element array
• too large target
• too small target
• the largest target
• the smallest target
• the half for odd array

Solutions

Binary Search

For input array nums[i : j], compare the middle number nums[(i + j)/2] and search the corresponding part. Running time is O(lg(n)):

class Solution {
    private int[] nums;
    private int   targ;
    
    public int searchInsert(int[] nums, int target) {
        int l = nums.length;
        
        if (l == 0) {return 0;}
        
        this.nums = nums;
        this.targ = target;
        
        return binarySearch(0, nums.length-1);
    }
    
    private int binarySearch(int i, int j) {
        if (i == j) {
            boolean c1 = (this.nums[i] == this.targ);
            boolean c2 = (this.nums[i] < this.targ);
            return c1 ? i : (c2 ? i+1 : i);
        }
        
        int m = (i + j) / 2;
        
        i = (this.targ <= this.nums[m]) ? i : m + 1;
        j = (this.targ <= this.nums[m]) ? m : j;
        
        return binarySearch(i, j);
    }
}