Binary Search

문제

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.

예시

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists 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 <= 104
• -9999 <= nums[i], target <= 9999
• All the integers in nums are unique.
• nums is sorted in an ascending order.

1차 풀이 코드(이진탐색 X) - 248ms / 15.6 MB

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for num in nums:
            if target == num:
                return nums.index(target)
            
        return -1

잠깐.. .index()만 활용해서 풀 수 있을 것 같다

2차 풀이 코드(.index()만) - 232ms / 15.6 MB

class Solution:
    def search(self, nums, target):
        try:
            return nums.index(target)
        except ValueError:
            return -1

이진탐색 문제라는 것을 잊지 않고...

3차 풀이 코드(이진탐색 O) - 240 ms / 15.5 MB

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