Binary Search Examples

[esthicodes]

class Solution(object):
    def search(self, nums, target):
# self is a class of method "Solution".
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        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

[esthicodes]

#brute force

time complex O(N)

#space complex O(McN)

i O(1) -> constant

def index_equals_value_search1(arr):
for i in xrange(len(arr)):
if i == arr[i]:
return i
return -1

def index_equals_value_search(arr):
# your code goes here
lo = 0
hi = len(arr) - 1

while lo <= hi:
  md = (lo+hi) / 2
  if arr[md] < md:
    lo = md + 1
    
  elif (arr[md] == md) and ((md==0) or (arr[md-1] < (md-1))):
    return md 
  else:
    hi = md - 1
    
return -1 

https://leetcode.com/problems/binary-search/

Binary search - youtube

def search(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
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

https://www.youtube.com/watch?v=P3YID7liBug

[MichelleObamaJ]

何の話しか私ぜんぜんわからない でもきっと 意味のあるものだと信じてる 2023년 4월 27일 (목) 오전 8:30, hona ***@***.***>님이 작성:

…

class Solution(object): def search(self, nums, target): # self is a class of method "Solution". """ :type nums: List[int] :type target: int :rtype: int """ 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 — Reply to this email directly, view it on GitHub <#230>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/A5JJWBNSZ5KSIEJ442QDCY3XDGV2HANCNFSM6AAAAAAXNC43VE> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[MichelleObamaJ]

Hoeun, where are you? Are you OK? Did I do wrong? Are you feel terrible? Please call me I will go We were supposed to meet this week. Let's eat delicious things and talk what happened. I am sorry that I didn't think about you.. please back me message!!!!!