BinarySearch

704. Binary Search
Easy
9.6K
193
Companies
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.


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
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.


My Solution: (note that the time complexity of my solution is pretty bad, so it needs improvement, so this is a working progress)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i, j in enumerate(nums): #turning nums list into index and value pairs
            if j == target: #if the value is equal to target, return corresponding index
                return i
        return -1 #if we go through the entire list and don't find any j's equal to target, return -1 as stated in the problem if does not exist
        
        
A better way to solve:

#in this approach, we divide the list in half and half again until we find the target or return -1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        #the reason we use <= instead of < is because when left and right become equal, the search space has been reduced to a single element. If the target element happens to be equal to this single element, the algorithm should still return its index.
        while left <= right:
            mid = (left + right) // 2 #finding the middle element of the list prioritizing left side: [-1, 0, 3, 5, 9, 12] - middle would be 3, not 5 if left = 0 and right = 5 because left and right are integers representing indicies.
            if nums[mid] == target:
                return mid
            elif nums[mid] < target: #if nums[mid] is smaller than the target, we know that target can only exist in the right half of the range, so left = mid + 1 narrows down the search range to the right half of the list
                left = mid + 1
            else: #if nums[mid] is bigger than target, target can only exist in left half of range, so right = mid - 1 narrows down search to left half of list
                right = mid - 1
        return -1
        
        #the general approach is dividing the problem in a half and half again until we find the element we are looking for or returning -1 (malan's lecture from harvard cs50)


another solution:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right: # = is necessary so that, in case the target equals the middle index itself, it's not being ignored by the looping condition.
            middle = left + (right - left) // 2 #this could also be middle = right - (right - left) // 2 as well
            if nums[middle] == target:
                return middle
            elif nums[middle] < target:
                left = middle + 1
            else:
                right = middle - 1
        return -1



8/13/23 (better formatted solution):

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        #already sorted
        left, right = 0, len(nums) - 1 #change is here, taking up one less line of code
        while left <= right: #= is included since there may be the pointer where left and right are equal that also happens to be equal to the target that we are looking for 
            middle = (left + right) // 2 #avoids issues with floating point integers since // deals with integer division, so the result will be rounded down
            if nums[middle] == target: #we found the target, so return 
                return middle
            elif nums[middle] < target: 
                left = middle + 1
            else:
                right = middle - 1
        return - 1

#12/2/23 refresher (my solution):

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        nums.sort()
        l = 0
        r = len(nums) - 1
        while l <= r: # we need <= because of when nums = [5] and target = 5
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            elif target > nums[mid]:
                l = mid + 1
            elif target < nums[mid]:
                r = mid - 1
        return -1



#2/1/24 refresher:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        #r = len(nums) - 1, not target!!!!
        r = len(nums) - 1
        while l <= r:
            mid = (l + r) // 2 
            if nums[mid] == target:
                return mid
            #if our current element is bigger than target, then we shrink the window by moving right pointer to mid - 1, not mid pointer
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return -1



#2/4/24 refresher:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        #we know our array is sorted
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return -1

#3/20/24 refresher:

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

#3/23/24:

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

#4/14/24:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        #we know the input array is already in ascending order, so we can just run a binary search
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                r = mid - 1 
            else:
                l = mid + 1
        return -1

#5/14/24 refresher:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        #since we know the array is sorted in ascending order, we can just run our binary search
        l, r = 0, len(nums) - 1 #already sorted - l and r are indicies
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return -1

#6/21/24 review:

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