Case study: search in rotated sorted array

March 31, 2020

Introduction

It is time for me to work on something challenging, write bug-free code as a 54 year old Chinese. Today I interviewed a top performer in his 20s, and I do think that he is very sharp and very concentrated on every detail of algorithm. He is currently working for Facebook. My case study will show how to write a solution in his way, I should make sure that I can have such performance whatever I do.

Case study

Will continue later.

Here is the gist, and I did add my review with comments and questions.

	import java.io.*;
	import java.util.*;
	class Solution {
	public static void main(String[] args) {
	Solution s = new Solution();
	int[] nums = {7, 9, 10, 1, 3, 5};
	int[] nums1 = {1, 3, 5, 7, 9, 10};
	int[] nums2 = {2, 1};
	System.out.println(s.getIndex(nums, 3));
	System.out.println(s.getIndex(nums, 6));
	System.out.println(s.getIndex(nums1, 9));
	System.out.println(s.getIndex(nums2, 1));
	}
	public int getIndex(int[] nums, int t) {
	int len = nums.length;
	if(len == 0) {
	return -1;
	}
	int st = 0, ed = len - 1;
	// st mid ed
	// st ed
	while(st + 1 < ed) { // if the array only have element -> exclude in while loop
	int mid = st + (ed - st) / 2;
	//int mid = (st + ed) / 2;
	if(nums[mid] == t) { // it is check middlevalue
	return mid;
	}
	//[start, end] -> [start, mid), mid, (mid, end]
	// exclude one number in every step -> design algorithm
	if(nums[mid] > nums[st]) { // ascending order at least length of range > 1
	if(nums[st] <= t && t < nums[mid]) {
	ed = mid; // check - mid - exclude mid, include mid / out of range concern: mid - 1
	} else {
	st = mid;
	}
	} else {
	if(nums[mid] < t && t <= nums[ed]) {
	st = mid;
	} else {
	ed = mid;
	}
	}
	}
	// <- do extra checking st/ end
	if(nums[st] == t) {
	return st;
	}
	if(nums[ed] == t) {
	return ed;
	}
	return -1;
	}
	}

view raw SearchInRotatedSortedArray.java hosted with ❤ by GitHub