0704. Binary Search

Easy | Array + Binary Search | 228 ms (91.88%), 15.5 MB (68.27%)

❓ Problem Statement

Source: LeetCode - Binary Search GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

Constraints:

• 1 <= nums.length <= 10^4

• -10^4 < nums[i], target < 10^4

• All the integers in nums are unique.

• nums is sorted in ascending order.

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

💡 Ideas

Standard Binary Search Problem.

Boundary / Search Space

Left (Minimum) = 0 Right (Maximum) = len(array) (last element could be the answer)

Condition

While Loop = Left < Right Return = array[mid] == target number

Return Value

Index or -1 (not found)

🤖 Python3

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # (base case)
        if len(nums) == 1: return 0 if nums[0] == target else -1
        
        # ==================================================
        #  Array + Binary Search                           =
        # ==================================================
        # time  : O(log(n))
        # space : O(1)

        l, r = 0, len(nums)
        while l < r:
            mid = (l + r) // 2
            
            if nums[mid] == target: return mid
            elif nums[mid] > target: r = mid
            elif nums[mid] < target: l = mid + 1
                
        return -1

🤖 Java

class Solution {
    /**
     * @time  : O(log(n))
     * @space : O(1)
     */
    
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        
        while(left < right) {
            int mid = (left + right) / 2;
            
            if(nums[mid] == target) {
                return mid;
                
            } else if(nums[mid] > target) {
                right = mid;
                
            } else if(nums[mid] < target) {
                left = mid + 1;
            }
        }
        
        return -1;
    }
}