LeetCode解題報告--Search for a Range

LeetCode解題報告--Search for a Range

題目：

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
點擊解題：Search for a Range

分析：題意要求找目標數組在出已排序數列的范圍。
題目難度不大，注意時間復雜度O(logn)，是該題的關鍵，三種解題思路：
1）暴力法直接遍歷（超時）：直接用for循環從左到右遍歷，時間復雜度為O(n),超時。先找記錄第一次nums[i] = target，array[0] = i,之後繼續遍歷,直至nums[i] != target,array[1] = i。
2）二分查找法（可行）：先找到nums[i] == target,不管i是左邊界還是右邊界，或是中間值，即找到第一個nums[i] = target, 之後在找到的i基礎上，向右遍歷找到右邊界，向左遍歷，找到左邊界。注意當找到第一個i =0 （或 i = nums.length - 1）,則左（或右）邊界找到，只需找右（或左）邊界，加個判斷。
3）雙指針發(可行)：雙指針left和right分別指向數組的起始，即left = 0,right = nums.length - 1,之後,先從左向右遍歷，找到第一個nums[i] = target,left = i, 此時left為左邊界；接著再從右向左遍歷，找到第一個nums[i] = target,right = i,此時right為右邊界。

如下示意圖示：

Java代碼：Accepted
Binary Search:

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        //term, termq for termporary variable, save the first middle
        int tem = 0;
        int tem1 = 0;
        //sign whether find target
        int flag = 0;
        int[] array = new int[] { -1, -1 };

        //Binary search to find first middle nums[middle] = target
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] == target) {
                tem = middle;
                tem1 = middle;
                flag = 1;
                break;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }

        //if not return[-1,-1]
        if (flag == 0) {
            return array;
        }

        //find the right boundary
        if(tem != nums.length - 1){
            while (tem < nums.length) {
                if ((tem + 1 < nums.length) && nums[tem] == nums[tem + 1]) {
                    tem++;
                } else {
                    array[1] = tem;
                    break;
                }
            }
        }else{
            array[1] = tem;
        }

        //find left boundary
        if(tem1 != 0){
            while (tem1 > -1) {
                if ((tem1 - 1 > -1) && nums[tem1] == nums[tem1 - 1]) {
                    tem1--;
                } else {
                    array[0] = tem1;
                    break;
                }
            }
        }else{
            array[0] = tem1;
        }

        return array;
    }
}

Tow Points Search:

public class Solution {
    public int[] searchRange(int[] nums, int target) {

        int[] array = new int[]{-1,-1};

        //tow points for search nums[left] == target and nums[right] == target
        int left = 0;
        int right = nums.length - 1;
        //flagL for left index is found and flagR for right index is found
        int flagL = 0;
        int flagR = 0;

        //Find left index
        while(left <= right){

            if(flagL == 0 && nums[left] == target){
                array[0] = left;
                flagL = 1;
                break;
            }else{
                left ++;
            }

        }

        //Find right index
        while(right >= left){

            if(flagR == 0 && nums[right] == target){
                array[1] = right;
                flagR = 1;
                break;
            }else{
                right --;
            }
        }

        //No find target
        if(flagL == 0 && flagR == 0){
            return array;
        }

        return array;
    }
}

Python代碼 Accepted：
Two Points Search：

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        #array for the result
        array = [-1,-1]
        #flagL for left index is found
        flagL = 0
        #flagR for right index is found
        flagR = 0

        #two points left and righr
        left = 0
        right = len(nums) - 1

        #found left index
        while(left <= right):
            if(nums[left] == target):
                array[0] = left
                flagL = 1
                break
            else:
                left += 1
        #found right index    
        while(right >= left):
            if(nums[right] == target):
                array[1] = right
                flagR = 1
                break
            else:
                right -= 1
        #no found target
        if(flagL == 0 and flagR == 0):
            return array

        return array