singularity

singularity 🔎

704. ✅ Binary Search

O(log n)

def BinarySearch(target, sortedLyst):
    left = 0
    right = len(sortedLyst)-1

    while left <= right:
        midpoint = (left + right) // 2
        if target == sortedLyst[midpoint]:
            return midpoint
        elif target < sortedLyst[midpoint]:
            right = midpoint - 1
        else:
            left = midpoint + 1
            
    return -1
print(BinarySearch(11,[-2, -1,1,2,3,4,5,11,19,22,90]))

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
    let mut l: i32 = 0;
    let mut r: i32 = (nums.len() - 1) as i32;

    while l <= r {
        let M = ((l + r) / 2) as usize;  // Convert to usize for indexing
        
        if target == nums[M] {
            return M as i32;
        } else if target < nums[M] {
            r = M as i32 - 1;  // Can be negative safely
        } else {
            l = M as i32 + 1;
        }
    }
        -1
    }
}

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut l = 0usize;
        let mut r = nums.len();

        while l < r {
            let m = l + (r - l) / 2;
            match nums[m].cmp(&target) {
                std::cmp::Ordering::Equal => return m as i32,
                std::cmp::Ordering::Greater => r = m,
                std::cmp::Ordering::Less => l = m + 1,
            }
        }

        -1
    }
}

[binary search] [two pointers]