March 30, 2020 - mock interview as an interviewer, 10:00 PM interviewee wrote bug-free code

SearchInRotatedSortedArray.java

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;
  }
}