[Leetcode] 704. Binary Search

📄 Description

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 write an algorithm with O(log n) runtime complexity.

정렬된 nums를 입력받아 이진 검색으로 target에 해당되는 인덱스를 찾아라.

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

🔨 My Solution

• This is the Iterative implmentation of Binary Search.

💻 My Submission

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1
        
        while left<=right:
            mid=left + (right-left)//2
            if target==nums[mid]:
                return mid
            # If x is greater, ignore left half
            elif target>nums[mid]:
                    left = mid+1
            # If x is greater, ignore right half
            else:
                right = mid-1
                
        return -1

💡 What I learned

There is TWO ways to implement Binary Search.

👉 [1. Recursive] - 재귀 풀이

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1
        
        def dfs(nums, l, r, target):
          if l<=r:
              mid=l+(r-l)//2
              if target==nums[mid]:
                  return mid
              # If element is smaller than mid, then it
        	  # can only be present in left subarray
              elif target>nums[mid]:
                  dfs(arr, mid+1, r, target)
              # Else the element can only be present
        	  # in right subarray
              else:
              	  dfs(arr, l, mid-1, target)
          else:
              return -1

👉 [2. Iterative] - 반복 풀이

My solution was "Iterative" implementation for Binary Search.

💭 My question

Then, what's the difference between "Iterative" approach and "Recursive" approach?

Recursion vs Iteration, What's the difference?

💭 Another Approach

👉 Using Binary Search Module bisect() - 모듈 사용

파이썬에서는 이진 검색을 직접 구현할 필요가 없다. 이진 검색 알고리즘을 지원하는 bisect 모듈을 기본적으로 제공한다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
		index = bisect.bisect(nums, target)
        
        if index<len(nums) and nums[index]==target:
        	return index
        else:    
        	return -1

💡 About bisect()

정렬된 리스트에 새로운 아이템 삽입 후에 다시 정렬할 필요 없도록 관리할 수 있도록 지원하는 모듈이다.
기본적인 이진 분할 알고리즘을 사용하기 때문에 bisect라고 불린다.

📌 bisect.bisect_left( )

정렬된 a에 x를 삽입할 위치, 좌측으로 삽입되는 인덱스를 반환한다.
찾아낸 값의 해당 위치 인덱스를 리턴

📌 bisect.bisect_right( ), bisect.bisect_right( )

정렬된 a에 x를 삽입할 위치, 좌측이 아닌 우측으로 삽입되는 인덱스를 반환한다.
찾아낸 값의 다음 인덱스를 리턴

References

• https://leetcode.com/problems/binary-search/
• https://www.code-recipe.com/post/binary-search
• https://www.geeksforgeeks.org/binary-search/
• https://docs.python.org/ko/3/library/bisect.html
• 파이썬 알고리즘 인터뷰(95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트), 박상길 지음
• https://wikidocs.net/105425