704. Binary Search(Easy)

문제

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must wrtie an algorithm with O(lon n) runtime complexity.

Example 1

Input : nums = [-1,0,3,5,9,12], target = 9
Output : 4
Explanation : 9 exits in nums and its index is 4

Example 2

Input : nums = [-1,0,3,5,9,12], target = 2
Output : -1
Explanation : 2 does not exist in nums so return -1

Constraints

• 1 <= nums.length <= 10^4
• -10^4 < nums[i], target < 10^4
• All the integers in nums are unique.
• nums is sorted in ascending order.

이진탐색

정렬되어 있는 자료구조(list)에서 특정 값(target)을 빠르게 찾는 알고리즘
Ex. [-1, 0, 3, 5, 9, 12]

1. left = 0 (배열의 첫 원소), right = n-1 (배열의 마지막 원소) 로 시작한다.
2. left와 right의 중간 index를 mid라고 할 때,

3. 찾고자 하는 값이 mid번째 원소와 같은 경우(list[mid] == target) 인 경우 결과를 출력하고 종료한다.
4. 찾고자 하는 값이 mid번째 원소보다 작은 경우(list[mid] > target), left~mid-1 사이에 값이 존재함을 알 수 있다.
5. 찾고자 하는 값이 mid번째 원소보다 큰 경우(list[mid] < target), mid+1~right 사이에 값이 존재함을 알 수 있다.

6. target을 찾을 때까지, 2-5를 반복한다.
7. left가 right보다 클 때까지(left > right), target을 찾지 못하면 target이 배열에 없다는 의미이다.

코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 오름차순 정렬된 리스트 nums
        # 찾는 숫자 target
        left = 0
        right = len(nums) - 1
        
        while left <= right :
            mid = (left + right) // 2
            if nums[mid] == target :
                return mid
            elif nums[mid] < target :
                left = mid + 1
            else :
                right = mid - 1
        return -1