알고리즘/리트코드
34. Find First and Last Position of Element in Sorted Array
창고
2021. 6. 16. 13:37
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
Find First and Last Position of Element in Sorted Array - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
특정 원소를 찾는데, 중복된 조건에서 가장 끝과 끝쪽에 있는 원소 찾기.
- 이진 탐색 활용
- 부등호를 어떻게 사용하느냐에 따라서 탐색 방향이 결정된다.
- 기존 이진 탐색의 if(arr[mid] = target) return target; 과 같이, target을 발견하면 바로 return하는 꼴이 아님.
target이 중복되므로, if(arr[mid] = target) idx = target; 을 통해서 idx를 계속해서 업데이트 한다.
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/discuss/14734/Easy-java-O(logn)-solution