Function leetcode_for_rust::cd0033_search_in_rotated_sorted_array::search

pub fn search(nums: Vec<i32>, target: i32) -> i32

Solutions

Approach 1: Binary Search

• Time complexity: O(logn)

• Space complexity: O(1)

• Runtime: 0 ms

• Memory: 2.5 MB

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        if nums.is_empty() { return -1; }

        let mut low = 0;
        let mut high = nums.len() - 1;

        while low <= high {
            let mid = low + ((high - low) >> 1);
            if nums[mid] == target { return mid as i32; }

            // left half is sorted
            if nums[low] <= nums[mid] {
                // target is in the left half array
               if nums[low] <= target && target <= nums[mid] {
                   high = mid - 1;
                }  else {
                    low = mid + 1;
                }
            } else { // right half is sorted
                // target is in the right half array
                if nums[mid] <= target && target <= nums[high] {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        -1
    }
}