参见编程珠玑chap4 chap9，和编程之美3.3

 

 

 

给定一个有序（不降序）数组arr,，

1. 求任意一个i使得arr[i]等于t，不存在返回-1

 

不变式：x[low]< =t<=x[high]

 

 

int biSearch(int *arr, int low, int high, int t){    int mid;     while(low<=high)    {        mid=low+(high-low)/2;        if(arr[mid]==t)        {            return mid;        }        else if(arr[mid]>t)        {           high=mid-1;        }        else        {            low=mid+1;        }    }    return -1;}

　　

 

2. 如存在重复元素，求最小的i使得arr[i]等于t，不存在返回-1

 

不变式：x[low]< t<=x[high]， return high

 

1 int biSearch(int *arr, int start, int end, int t) 2  3 { 4  5     int high, low, mid; 6  7     //x[l]
     
      
       =end+1 || arr[high]!=t)38 39     {40 41         return -1;42 43     }44 45     else46 47     {48 49         return high;50 51     }52 53 }
      
     

 

 

 

3. 如存在重复元素，求最大的i使得arr[i]等于t，不存在返回-1

 

不变式：x[low]<= t<x[high]， return low

 

1 int biSearch(int *arr, int start, int end, int t) 2  3 { 4  5     int high, low, mid; 6  7     //x[l]<=t

 

 

4. 求最大的i使得arr[i]小于t，不存在返回-1；

 

不变式： x[low] <t<=x[high], return low

 

1 int biSearch(int *arr, int start, int end, int t) 2  3 { 4  5     int high, low, mid; 6  7     //x[l]
     
      
       t)38 39     {40 41         return -1;42 43     }44 45     else46 47     {48 49         return low;50 51     }52 53 }
      
     

 

 

 

5. 求最小的i使得arr[i]大于t，不存在返回-1；

不变式：x[low]<=t<x[high]，return high

略

 

测试程序：

1 #include 
     
       2  3 using namespace std; 4  5  6 void init(int *a, int n) 7 { 8     for(int i=0; i
      
       t)42     {43         return -1;44     }45     else46     {47         return low;48     }49 }50 51 int main()52 {53     int n=5;54     int arr[n];55 56     init(arr, n);57     print(arr, n);58     for(int i=-2; i