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

    點擊解題：Search Insert Position

    分析：從給定排好順序的數組，找出給定目標數字下標，存在則返回下標，不存在則返回目標數應該插入的位置下標，

LeetCode解題報告Search Insert Position

    提供兩個可行思路：

    1).二分查找

    a.存在情況，就是經典二分查找問題

    b.不存在情況，加個判別條件 nums[mid] < target && nums[mid + 1] > target 原因在于，如果存在target，則nums[mid]與target的關系必然存在三種 “>”,”<”和”==”。

    2).雙指針法

    雙指針法判斷條件多，基本原理是left,rigth雙指針分別指向nums首末元素，從左右兩邊分別開始判斷元素（nums[left],nums[right] ）與target的關系，則如果存在target，則nums[left(right)]與target的關系必然存在三種 “>”,”<”和”==”。以此為判斷標準，就可找到index

    至于暴力法也是可以求解，但會超時，我沒試過，雖然題目沒時間復雜度限制，但是應該是不允許。

    蓋提與Search for range思路相似，具體可參考該篇博客

    改題是二分查找的變形題目，會二分查找，就迎刃而解。

    Java代碼 Accepted:

    Binary Search:

<code class="hljs cs">public class Solution {    public int searchInsert(int[] nums, int target) {        //Binary Search        int left = 0;        int right = nums.length - 1;        while(left <= right){            int middle = (left + right) / 2;            if(nums[middle] == target)                return middle;            else if(nums[middle] < target){                left = middle + 1;            }else if(nums[middle] > target){                right = middle - 1;            }else if(nums[middle] < target && nums[middle + 1] > target){                return middle;            }        }         return left;    }}</code>

    Double Points Search:

<code class="hljs axapta">public class Solution {    public int searchInsert(int[] nums, int target) {        //double points search        int left = 0;        int right = nums.length - 1;        //flag for whether nums[left] > target or nums[right] < target        int flag = 0;        //save index of target        int index = 0;        while(left <= right){            //when nums's length == 1            if(left == right){                if(nums[left] > target)                    return left;                else if(nums[left] < target)                    return left + 1;                else                    return left;            }            //find target,then save left to index            else if(nums[left] == target){                index = left;                break;            }            //find target,then save right to index            else if(nums[right] == target){                index = right;                break;            }            //when nums[left] < target, if nums[left + 1] > target, target not exsist           else if(nums[left] < target){                left ++;                flag = 1;            }            else if(flag == 1 && nums[left] > target){                index = left;                break;            }            //when nums[right] > target, if nums[right - 1] < target, target not exsist            else if(nums[right] > target){                right --;                flag = 1;            }            else if(flag == 1 && nums[right] < target){                index = right;                break;            }        }        return index;    }}</code>

    Python 代碼：

    Binary Search:

<code class="hljs python">class Solution(object):    def searchInsert(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: int        """        left = 0        right = len(nums) - 1        while(left <= right):            mid = (left + right) / 2            if(nums[mid] == target):                return mid            elif(nums[mid] < target):                left = mid + 1            elif(nums[mid] > target):                right = mid - 1            elif(nums[mid] < target and nums[mid + 1] < target):                return mid + 1        return left</code>