vamsu
8/11/2018 - 9:04 PM

Circular sorted search

Circular sorted search

import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args) {
    Solution solution = new Solution();
    int[][] input = {
          null,
          {},
          {1},
          {5352,2111},
          {6,7,8,9,3,5},
          {422,534,119,210,323}
        };
    int[][] searching ={
      {-1},
      {2},
      {1},
      {2111, 5352},
      {1,3,9,6,7,8},
      {210,323,321}
      };
    for(int i=0;i<input.length;i++){
      for(int j=0;j<searching[i].length;j++){
       System.out.println("Input: " + Arrays.toString(input[i]) + 
                        ", Searching: "+ searching[i][j] + ", Result: " + 
                      solution.circularBinarySearch(input[i],searching[i][j]));
      }
    }

  }
  
  public int circularBinarySearch(int[] input, int searchingFor) {
    if(input == null || input.length < 1) {
      return -1; 
    }
    int start = 0;
    int end = input.length-1;
    while (start <= end){
      int mid = start + (end-start)/2;
      if(input[mid] == searchingFor){
        return mid;  
      }
      
      if (input[start] > input[end] ) {
        if(searchingFor > input[start]){
          end = mid-1;
        } else {
          start = mid+1;
        }
      } else {      
        if (searchingFor > input[mid]) {
          start = mid+1; 
        } else {
          end = mid-1;
        }      
      }
    }
    return -1;
  }
}