[1스4코2파] #154. LeetCode pattern 704. Binary Search

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (154일차)
[4코1파] 2023.01.13~ (145일차)
[1스4코1파] 2023.04.12~ (56일차)
[1스4코2파] 2023.05.03 ~ (35일차)

Today :

2023.06.05 [154일차]
LeetCode Patterns
704. Binary Search
https://leetcode.com/problems/binary-search/

704. Binary Search

문제 설명

문제 풀이 방법

int 형 데이터타입 원소로 구성된 nums 배열에서
target 값을 찾는 문제
target 값이 있으면 해당 배열에서의 target의 index를 return 하고 없으면 -1을 return 한다.

시간복잡도 O(log n)으로 풀어야 하는 문제이므로
단순하게 for문 loop로는 풀면 X

시간복잡도 log n으로 풀 수 있는 방법은 문제 제목과 같이 binary Search를 통해서 푼다.

총 3개의 변수를 이용하는 데 start, end, mid 이다.

two point로 start, end를 지정하고,
start는 배열의 첫번째, end는 배열의 마지막(길이) 만큼 그리고 start와 end의 정 가운데 값 mid 이다.

while문으로 start 가 배열의 길이 (end) 보다 작거나 같을 때까지의 조건으로 도는데, mid와 찾을 target값을 비교해서 mid가 작으면 start 포인트를 mid보다 +1, target보다 크다면 end 포인트를 mid-1로 설정해서 좁혀나간다.

내 코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start, end = 0, len(nums)-1
        answer = -1
        while start<=end:
            mid = (start+end)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                start = mid+1
            else:
                end = mid-1
        return answer

증빙

여담

휴 6시 완