Search element in circularly sorted array .(Java Code)

Problem :  Search index of element in circularly sorted array . Elements are not repeated.

Observations :

Whenever array is sorted always look out for usage of binary search for best worst performance .

Scanning array 

Iterate over array and just look for element once we get break the loop.

Time complexity , T(n) = n


Tweaked binary search 

Sorted array -->  1,2,3,4,5,6,7,8,9,10,11

intput -->

After one rotation --> 11,1,2,3,4,5,6,7,8,9,10

if we are searching for 9
Output --> 8


For mid pivot ( ( high+low )/2) of 5 right half is sorted . while left is not sorted .
So for any rotation one half will be sorted and other will not be .
Based on this fact we need to direct binary search to the part of circular array .


Time complexity ,  T(n) = log2(n)


Java Code 

package com.salpe.sort;

import org.junit.Assert;
import org.junit.Test;

public class BinarySearchUtils {

 @Test
 public  void testSuccess() {

  int[] arr = new int[] {1,2,3,4,5,6,7,8,9,10,11};

  Assert.assertEquals(4, searchCircularArray(arr, 5));

  arr = new int[] {11,1,2,3,4,5,6,7,8,9,10};

  Assert.assertEquals(5, searchCircularArray(arr, 5));

  arr = new int[] {10,11,1,2,3,4,5,6,6,7,8,9};

  Assert.assertEquals(6, searchCircularArray(arr, 5));

 }
 
 /**
  * <p>
  * mid always divides array between one sorted and one unsorted sub arrays.
  * 
  * <p>
  * array rotated by 2 --> 11,10,1,2,3,4,5,6,7,8,9
  * <p>
  * mid element is 4 left of 4 is not sorted , right of 4 is sorted
  * 
  * <p>
  * If it is sorted then check lo and hi to check value in it else go to
  * other unsorted half.
  * <p>
  * 
  * T(n) = log2(n)
  * 
  * @param arr
  * @param val
  * @return
  */
 public static int searchCircularArray(int[] arr, int val) {

  int lo = 0;
  int hi = arr.length - 1;

  while (lo <= hi) {

   // find mid pivot
   int mid = (lo + hi) / 2;

   // if mid matches game over
   if (arr[mid] == val) {

    return mid;

   }
   // right array sorted
   else if (arr[mid] < arr[hi]) {

    // check value contains in sorted right
    if (val > arr[mid] && val <= arr[hi]) {

     lo = mid + 1;

    } else {

     hi = mid - 1;
    }

   }
   // left array sorted
   else {

    // check value contains in sorted left
    if (val < arr[mid] && val >= arr[lo]) {

     hi = mid - 1;

    } else {

     lo = mid + 1;
    }
   }

  }

  // oops no match found
  return -1;

 }

}