public class Iterative {    /**    Normal Binary Search for sorted array like : 1,2,3,4,5,6,7,8,9,10,11    Complexity: O(LogN)    PS: element can be duplicated    */    static public int binarySearch(int[] array, int target){        int left = 0, right = array.length - 1;        while (left <= right){            int middle = (right + left) / 2;             if (array[middle] == target)                return middle;             if (array[middle] > target)                right = middle - 1;            else                left = middle + 1;        }        return -1;    }    /**    If the array is rotated-sorted-array, like: 5,6,7,8,9,10,1,2,3,4. We can alter the original binary search for this    PS:the array must not have duplcations, otherwise the complexity will be O(N)    Complexity: O(LogN)    */    static public int rotatedBinarySearch(int[] array, int target){        int low = 0;        int high = array.length - 1;        int mid = 0;        while (low <= high) {            mid = (low + high) / 2;            if (array[mid] == target) return mid;            else {                if (array[low] <= array[mid]) {  //decide left part is longer                    if (target >= array[low] && target < array[mid]) {                        high = mid - 1;                    } else {                        low = mid + 1;                    }                } else {    //right part is longer                    if (target <= array[high] && target > array[mid]) {                        low = mid + 1;                    } else {                        high = mid - 1;                    }                }            }        }        return -1;    }}

TEST(binarySearch,BasicTest){    Iterator iter;    int array[] = {1,2,3,4,5,6,7,8,9,10};    EXPECT_TRUE(4 == iter.Search(array,4));    EXPECT_TRUE(5 == iter.Search(array,5));    EXPECT_TRUE(6 == iter.Search(array,6));    EXPECT_TRUE(7 == iter.Search(array,7));        EXPECT_TRUE(-1 == iter.Search(array,11));    EXPECT_TRUE(-1 == iter.Search(array,12));    EXPECT_TRUE(-1 == iter.Search(array,0));}TEST(rotatedBinarySearch,BasicTest){    Iterator iter;    int array[] = {5,6,7,8,9,10,1,2,3,4};    EXPECT_TRUE(4 == iter.Search(array,4));    EXPECT_TRUE(5 == iter.Search(array,5));    EXPECT_TRUE(6 == iter.Search(array,6));    EXPECT_TRUE(7 == iter.Search(array,7));        EXPECT_TRUE(-1 == iter.Search(array,11));    EXPECT_TRUE(-1 == iter.Search(array,12));    EXPECT_TRUE(-1 == iter.Search(array,0));}