【Binary Search】二分查找（普通二分查找；重复元素返回第一个索引的二分查找；查找范围为2次幂的二分查找）

/* common binarySearch */
int commonbinarySearch(int arr[], int len, int key){
    int index = -1;
    int low=0, high=len-1, mid;
    while(low <= high){
        mid = (low + high) / 2;
        if(arr[mid] == key){
            index = mid;
            break;
        }
        else if(key > arr[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
    return index;
}

/* repeat binary Search
 when there are repeated elements in array
 commonBinarySearch func will return index randomly
 but repeatBinarySearch will return first index*/
 int repeatBinarySearch(int arr[], int len, int key){
     int index = -1;
     if(len == 0)
        return -1;
     int low=0, high=len-1, mid;
     while(low != high){
        mid = (low+high) / 2;
        if(arr[mid] < key)
            low = mid + 1;
        else
            high = mid;
     }
     if(arr[low] == key)
        index = low;
     return index;
 }

/* special Binary Search need findInitRange(len) to get first range
 according to len */
 int findInitRange(int len){
     if(len == 1)
        return 0;
     int mul = 1;
     while(mul*2 < len){
        mul *= 2;
     }
     return mul;
 }
 /* special Binary Search
 range is always 2^x
 if sub(index1-index2) = 2^x,then there are odd elements between index1,index2 */
 int specialBinarySearch(int arr[], int len, int key){
     int initRange = findInitRange(len);
     //print initRange
     printf("Init Range: %d\n", initRange);
     int index = -1;
     if(len == 0)
        return -1;
     int low = 0, incre = initRange, nextIncre;
     //determine initial search range
     if(arr[low+incre] < key)
        low = len-1-incre;
    while(incre != 0){
        nextIncre = incre / 2;
        if(arr[low+nextIncre] < key){//just left only two neighbor elements
            low = low + nextIncre + 1;
        }
        incre = nextIncre;
    }
    if(arr[low] == key)
        index = low;
    return index;
 }