Leetcode - Rust - Single Element in a Sorted Array

leetcode-rust-single-element-in-a-sorted-array.md

Problem: https://leetcode.com/problems/single-element-in-a-sorted-array/description/ Solution: https://leetcode.com/problems/single-element-in-a-sorted-array/solutions/4254843/rust-solution-using-binary-search/

Using binary search, seek middle. The idea is that since this is a sorted array, finding which side has the single element is just a matter of comparing adjacent items from the middle and the distance between middle and the edges.

For example, if the middle item and the item to the left is equal and the distance between the middle and the left is even, then the single element must not be on the left since the distance is an event number. It must be to the right.

impl Solution {
    pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
        if nums.len() == 1 {
            return nums[0];
        }

        let mut l: usize = 0;
        let mut r: usize = nums.len() - 1;
        let mut mid: usize = 0;
        let mut mid_index: usize = 0;
        let mut distance: usize = 0;

        while l <= r {
            if l == r {
                // Found it
                return nums[l];
            }

            // Find the mid
            mid = ((r - l) / 2) as usize;
            mid_index = l + mid;
            distance = (mid + 1) as usize;

            // Find which side has the single element
            if nums[mid_index] == nums[mid_index -1] {
                if distance % 2 == 0 {
                    // Item must be to the right
                    l = mid_index + 1;
                } else {
                    // Item must be to the left
                    r = mid_index - 2;
                }
            } else if nums[mid_index] == nums[mid_index + 1] {
                if distance % 2 == 0 {
                    // Item must be to the left
                    r = mid_index - 1;
                } else {
                    // Item must be to the right
                    l = mid_index + 2;
                }
            } else {
                // Found it
                return nums[mid_index];
            }
        }

        return 0;
    }
}