704, Binary Search

I Problem

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

Related Topics

• Array
• Binary Search

II Solution

macro_rules! mid_idx {
    ($left:expr, $right:expr) => {
        $left + (($right - $left) >> 1)
    };
}

Approach 1: Find the Exact Value

pub fn search(nums: Vec<i32>, target: i32) -> i32 {
    let mut left = 0;
    let mut right = nums.len();

    while left < right {
        let mid = mid_idx!(left, right);
        if target < nums[mid] {
            right = mid;
        } else if nums[mid] < target {
            left = mid + 1;
        } else {
            return mid as i32;
        }
    }

    -1
}

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length;

    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (target < nums[mid]) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }

    return -1;
}

Approach 2: Find Upper Bound

pub fn search(nums: Vec<i32>, target: i32) -> i32 {
    let mut left = 0;
    let mut right = nums.len();

    while left < right {
        let mid = mid_idx!(left, right);
        if nums[mid] <= target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    if left > 0 && nums[left - 1] == target {
        left as i32 - 1
    } else {
        -1
    }
}

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length;

    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    if (left > 0 && nums[left - 1] == target) {
        return left - 1;
    } else {
        return -1;
    }
}

Approach 3: Find Lower Bound

pub fn search(nums: Vec<i32>, target: i32) -> i32 {
    let mut left = 0;
    let mut right = nums.len();

    while left < right {
        let mid = mid_idx!(left, right);
        if target <= nums[mid] {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    if left < nums.len() && nums[left] == target {
        left as i32
    } else {
        -1
    }
}

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length;

    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (target <= nums[mid]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    if (left < nums.length && nums[left] == target) {
        return left;
    } else {
        return -1;
    }
}

Approach 4: Use built-in Tools

pub fn search(nums: Vec<i32>, target: i32) -> i32 {
    match nums.binary_search(&target) {
        Ok(idx) => idx as i32,
        Err(_) => -1,
    }
}

public int search(int[] nums, int target) {
    int idx = Arrays.binarySearch(nums, target);
    return idx < 0 ? -1 : idx;
}