Leetcode - 704. Binary Search

문제

주어진 배열중 target에 해당하는 값의 index를 리턴

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

해결 (by Rust)

match와 std::cmp::Ordering 사용하는 부분이 흥미로움.

• Vec의 cmp()는 Ordering 타입을 리턴함.
• Vec타입 indexing은 i32변수로 하면 안되고 usize변수로 해야함.
• nums.len()은 usize 타입이므로 i32로 형변환

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        use std::cmp::Ordering;        
        let mut left: i32 = 0;
        let mut right: i32 = nums.len() as i32 - 1;
        while left <= right {
            let mid: i32 = (left + right) / 2;
            match nums[mid as usize].cmp(&target) {
                Ordering::Equal => return mid,
                Ordering::Less => left = mid + 1,
                Ordering::Greater => right = mid - 1
            }
        }
        -1
    }
}

해결 (by C)

int bin_search(int *nums, int numsSize, int tgt)
{
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    
    while (left <= right) {
        mid = (left + right) >> 1;
        if (tgt == nums[mid])
            return mid;
        else if (tgt < nums[mid])
            right = mid - 1;
        else if (tgt > nums[mid])
            left = mid + 1;
    }
    return -1;
}

int search(int* nums, int numsSize, int target){
    return bin_search(nums, numsSize, target);
}