pub fn search(nums: Vec<i32>, target: i32) -> i32
Expand description
§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
}
}