[Q2:English] First and last index in sorted array

👇🏻 문제(이 정도는 해석X...귀찮,, 영어강의라 포스트도 영어로)

Given a sorted array of integers arr and an integer target, find the index of the first and last position of target in arr. In targer can't be found in arr, return [-1,-1].

For example, arr = [2,4,5,5,5,5,5,7,9,9], target = 5 👉🏻 output : [2, 6]

---

My ans

 

 

 [Method 1] 

# Logic

 

# Code

 

 

# Complexity

S(n) = O(1)

T(n) = O(n)

 

 

 

 

---

 [Method 2] 

How about using binary search? Because it is sorted already.

2022.05.18 - [Python/[Algorithm] 알고리즘] - Binary Search, 이진 탐색

Binary Search, 이진 탐색

 

# Logic

1️⃣ Find first position

 

2️⃣ Find last position using first position

Set last_idx = first_idx and Check with while loop.

or

Find with binary search like finding first position.

 

 

 

 

 

# Code

use 1 binary search / 2 binary search

 

 

 

 

# Complexity

T(n) = 2 * O(logn) = O(logn)

S(n) = O(1)