# [Leetcode] 704. Binary Search

limelimejiwonยท2022๋ 3์ 16์ผ
0

๋ชฉ๋ก ๋ณด๊ธฐ
23/67

## ๐ 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.

## ๐ญ 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