Binaary Search

704.Binary Search

Array

Binary Search

Problem Statement:

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:

Input:

nums = [-1,0,3,5,9,12]
target = 9

→

Output:

4

9 exists in nums and its index is 4

Algorithm:

1. Initialize pointers to start and end of array
2. Find middle element while low ≤ high
3. If target is less, search left half
4. If target is more, search right half
5. Return mid if found, -1 if not found

Complexity:

Time: O(log n) | Space: O(1)

Java Solution:

public int search(int[] nums, int target) {
    int low = 0;
    int high = nums.length - 1;
    
    // Remember <=
    while (low <= high) {
        int mid = (high - low)/2 + low;
        
        if (target < nums[mid]) 
            high = mid - 1;
        else if (target > nums[mid]) 
            low = mid + 1;
        else 
            return mid;
    }
    
    return -1;
}

Python Solution:

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

C++ Solution:

int search(vector<int>& nums, int target) {
    int low = 0;
    int high = nums.size() - 1;
    
    while (low <= high) {
        int mid = (high - low)/2 + low;
        
        if (target < nums[mid])
            high = mid - 1;
        else if (target > nums[mid])
            low = mid + 1;
        else
            return mid;
    }
    
    return -1;
}