LeetCode解題報告--Search Insert Position

LeetCode解題報告--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.
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

分析：從給定排好順序的數組，找出給定目標數字下標，存在則返回下標，不存在則返回目標數應該插入的位置下標。
提供兩個可行思路：
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:

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;
    }
}

Double Points Search:

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;
    }
}

Python 代碼：
Binary Search:

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