Case study: search in rotated sorted array

March 31, 2020

Here is the gist.

	import java.io.*;
	import java.util.*;
	/*
	* To execute Java, please define "static void main" on a class
	* named Solution.
	*
	* If you need more classes, simply define them inline.
	*/
	class Solution {
	public int findValueInRotatedArray(int[] nums, int target) {
	if(nums == null || nums.length == 0) {
	return -1;
	}
	int lo = 0;
	int hi = nums.length - 1;
	while(lo <= hi) {
	int mid = lo + (hi - lo) / 2;
	if(nums[mid] == target) {
	return mid;
	}
	// If left side is sorted.
	if(nums[lo] <= nums[mid]) {
	if(target >= nums[lo] && target <= nums[mid]) {
	hi = mid - 1;
	}
	else {
	lo = mid + 1;
	}
	} else {
	if(target > nums[mid] && target <= nums[hi]) {
	lo = mid + 1;
	} else {
	hi = mid - 1;
	}
	}
	}
	return -1;
	}
	public static void main(String[] args) {
	Solution solver = new Solution();
	int[] nums = new int[]{7, 9, 11, 1, 2, 5};
	int[] nums1 = new int[]{1, 2, 5, 7, 9, 11};
	System.out.println(solver.findValueInRotatedArray(nums, 2) == 4);
	System.out.println(solver.findValueInRotatedArray(nums, 8) == -1);
	System.out.println(solver.findValueInRotatedArray(nums1, 1) == 0);
	System.out.println(solver.findValueInRotatedArray(nums1, 11) == 5);
	System.out.println(solver.findValueInRotatedArray(nums1, 12) == -1);
	}
	}
	/*
	given an integer sorted array, rotated in unknown position, given a value, find index position of the array. If not found, return -1.
	[1, 3, 5, 7, 9, 11]
	rotated
	[7, 9, 11, 1, 2, 5], given a value 2, return 4;
	given a value 8, return -1
	bool findValueInRotate(int[] numbers, int target)
	*/

view raw SearchInRotatedSortedArray.java hosted with ❤ by GitHub