package com.interview.binarysearch;

/**
 * http://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/
 * This does not works if there are duplicates in the array.
 */
public class SortedAndRotatedArraySearch {

    public int search(int arr[],int search){
        
        int low =0;
        int high = arr.length-1;
        while(low <= high){
            int mid = (low + high)/2;
            if(arr[mid] == search){
                return mid;
            }
            
            if(arr[mid] < arr[high]){
                if(arr[mid] < search && search <= arr[high]){
                    low = mid+1;
                }else{
                    high = mid-1;
                }
            }else{
                if(search >= arr[low] && search < arr[mid]){
                    high = mid-1;
                }else{
                    low = mid+1;
                }
            }
        }
        return -1;
    }
    
    public static void main(String args[]){
        SortedAndRotatedArraySearch ras = new SortedAndRotatedArraySearch();
        int arr1[] = {1,2,5,6,7,8,11,21};
        System.out.print(ras.search(arr1, 1));
        System.out.print(ras.search(arr1, 5));
        System.out.print(ras.search(arr1, 22));
        System.out.println();
    
        int arr2[] = {18,21,1,2,5,6,7,8,10,15};
        System.out.print(ras.search(arr2, 1));
        System.out.print(ras.search(arr2, 5));
        System.out.print(ras.search(arr2, 10));
        System.out.print(ras.search(arr2, 14));
        System.out.println();

        int arr3[] = {7,8,15,17,18,21,1,2,5,6};
        System.out.print(ras.search(arr3, 1));
        System.out.print(ras.search(arr3, 5));
        System.out.print(ras.search(arr3, 10));
        System.out.print(ras.search(arr3, 7));
        System.out.print(ras.search(arr3, 6));
        System.out.print(ras.search(arr3, 16));
    }
}

@@ -41,146 +41,401 @@
 %0A * 
-http://www.geeksforgeeks.org/search-an-element-in-a-
+@author Tushar Roy%0A * Date 01/22/17%0A *%0A * Search in 
 sorted
--and-pivoted-
+ and rotated 
 array
-/%0A * This does not works if there are duplicates in the 
+. In one version duplicate is not allowed and%0A * in another version duplicate is allowed.%0A *%0A * Time complexity with no duplicate - O(logn)%0A * Time complexity with duplicates - O(n)%0A *%0A * https://leetcode.com/problems/search-in-rotated-sorted-array/%0A * https://leetcode.com/problems/search-in-rotated-sorted-
 array
-.
+-ii/
 %0A */
@@ -479,16 +479,74 @@
 arch %7B%0A%0A
+    /**%0A     * Duplicates are not allowed in arr.%0A     */%0A
     publ
@@ -582,25 +582,16 @@
 earch)%7B%0A
-        %0A
         
@@ -1232,24 +1232,1053 @@
 rn -1;%0A    %7D
+%0A%0A    /**%0A     * Duplicates are allowed in arr.%0A     */%0A    public boolean searchWithDuplicates(int%5B%5D arr, int search) %7B%0A        int low =0;%0A        int high = arr.length-1;%0A        while(low %3C= high)%7B%0A            int mid = (low + high)/2;%0A            if(arr%5Bmid%5D == search) %7B%0A                return true;%0A            %7D%0A            //if low is same as mid then increment low.%0A            if (arr%5Bmid%5D == arr%5Blow%5D) %7B%0A                low++;%0A            %7D else if (arr%5Bmid%5D == arr%5Bhigh%5D) %7B //if high is same as mid then decrement high.%0A                high--;%0A            %7D else if (arr%5Bmid%5D %3C arr%5Bhigh%5D) %7B%0A                if(arr%5Bmid%5D %3C search && search %3C= arr%5Bhigh%5D) %7B%0A                    low = mid + 1;%0A                %7D else %7B%0A                    high = mid - 1;%0A                %7D%0A            %7D else %7B%0A                if(search %3E= arr%5Blow%5D && search %3C arr%5Bmid%5D) %7B%0A                    high = mid - 1;%0A                %7D else %7B%0A                    low = mid + 1;%0A                %7D%0A            %7D%0A        %7D%0A        return false;%0A    %7D
 %0A    %0A    pu

update search in sorted rotated array