[Golang][Leetcode][Array]刷題系列-34-Binary Search

Steven included in Leetcode Golang

2021-07-09 332 words 2 minutes

Contents

34. Find First and Last Position of Element in Sorted

Array

Level : Medium

原題連結 : Click

題目 :

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example :

Note

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

以下是我自己的解法 - O(lgn)

Runtime: 4 ms, faster than 99.23% of Go online submissions for Find First and Last Position of Element in Sorted Array.

解題思路 :

這是一個經典的Binary Search變種題，通常Binary Search會有4大變種題

找到第一個值等於target的elements
找到最後一個值等於target的elements
找到第一個大於等於target的elements
找到最後一個值小於等於target的elements

而這題我的實現方法是用第1種與第2種個實現一個function，再回傳答案

 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

func searchRange(nums []int, target int) []int {
    return []int{searchFirstEqualElement(nums, target) , searchLastEqualElement(nums, target)}
}

func searchFirstEqualElement(nums []int, target int) int {
    
    low, high := 0, len(nums)-1
    
    for low <= high {
        
        mid := low + ((high-low) >> 1)
        
        if nums[mid] > target {
            high = mid - 1
        }else if nums[mid] < target {
            low = mid + 1
        }else {
            if mid == 0 || nums[mid-1] != target {
                return mid
            }
            high = mid -1
        } 
    }
    return -1
    
}

func searchLastEqualElement(nums []int, target int) int {
    
    low, high := 0, len(nums)-1
    
    for low <= high {
        
        mid := low + ((high-low) >> 1)
        
        if nums[mid] > target {
            high = mid - 1
        }else if nums[mid] < target {
            low = mid + 1
        }else {
            if mid == (len(nums)-1) || nums[mid+1] != target {
                return mid
            }
            low = mid + 1
        } 
    }
    return -1
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!