Search in Rotated Sorted Array

1package pkg5leetcode.blind75;2 3/*4 * Search in Rotated Sorted Array | LC 335 * APPROACH: Binary search identifying sorted half.6 * COMPLEXITY: Time O(log n), Space O(1)7 */8public class blind75_LC33SearchInRotatedSortedArray {9    static int search(int[] nums, int target) {10        int lo = 0, hi = nums.length - 1;11        while (lo <= hi) {12            int mid = lo + (hi - lo) / 2;13            if (nums[mid] == target) return mid;14            if (nums[lo] <= nums[mid]) {15                if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;16                else lo = mid + 1;17            } else {18                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;19                else hi = mid - 1;20            }21        }22        return -1;23    }24 25    public static void main(String[] args) {26        check(search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0) == 4, "case1");27        check(search(new int[]{4, 5, 6, 7, 0, 1, 2}, 3) == -1, "case2");28        System.out.println("all tests passed");29    }30 31    static void check(boolean cond, String name) {32        if (!cond) throw new AssertionError("FAILED: " + name);33        System.out.println("  PASS " + name);34    }35}