二分查找及扩展

面试常让写二分查找或其扩展的程序，以前总觉得很简单，但是真动手写起来，细节很多，容易出错的地方也很多，真是秒杀眼高手低的利器，本节就二分查找以及相关扩展程序都实现一下，同时将可能出错的地方以及需要注意的细节也一并说明，水平有限，欢迎补充。

内容如下：

1）二分查找元素key的下标，如无 return -1

2）二分查找返回key(可能有重复)第一次出现的下标，如无return -1

3）二分查找返回key(可能有重复)最后一次出现的下标，如无return -1

4）二分查找返回刚好小于key的元素下标，如无return -1

5）二分查找返回刚好大于key的元素下标，如无return -1

http://www.ahathinking.com/archives/179.html

看了这个写的后觉得很难理解，自己写了一个

1）二分查找元素key的下标，如无 return -1

#include <stdio.h>  
#define ARRAY_LEN(array) sizeof(array)/sizeof(array[0])  
 
int is_sort_asc(int array[], int length) 
{ 
    int i = 0; 
    if(length <= 0) 
    { 
        return -1; 
    } 
    for(i = 0; i < length - 1; i++) --------------------------------------->注意条件 
    { 
        if(array[i] > array[i+1]) 
        { 
            return -1; 
        } 
    } 
    return 0; 
} 
 
 
int binary_search(int array[], int left, int right, int key) 
{ 
    int mid = 0; 
    if(right <= 0) 
    { 
        return -1; 
    } 
     
    while(left <= right)     --------------------------------------->注意条件 
    { 
        printf("left = %d, right = %d\n", left, right); 
        mid = (left + right) >> 1;                              /*更好的写法是 mid = left + ((right - left) >> 1)*/ 
        printf("mid = %d, array[mid] = %d\n", mid, array[mid]); 
        if(array[mid] < key)  
        { 
            left = mid + 1; 
        } 
        else if(array[mid] > key) 
        { 
            right = mid - 1; 
        }    
        else 
        { 
            return mid; 
        } 
    } 
    return -1; 
} 
int main() 
{ 
    int tmp[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}; 
    int num = 0; 
    int i = 0; 
    int ret = -1; 
    printf("tmp array:"); 
    for(i = 0; i < ARRAY_LEN(tmp); i++) 
    { 
        printf(" %d", tmp[i]); 
    } 
    printf("\n"); 
    if(-1 == is_sort_asc(tmp, ARRAY_LEN(tmp))) 
    { 
        printf("tmp is not sort by asc\n"); 
        return -1; 
    } 
 
    num = 1; 
    ret = binary_search(tmp, 0, ARRAY_LEN(tmp) - 1, num); 
    if(-1 == ret) 
    { 
        printf("can not find the num %d\n", num); 
    } 
    else 
    { 
        printf("find key = %d in tmp[%d]\n", num, ret); 
    } 
    printf("\n"); 
    return 0; 
} 

#include <stdio.h>
#define ARRAY_LEN(array) sizeof(array)/sizeof(array[0])

int is_sort_asc(int array[], int length)
{
 int i = 0;
 if(length <= 0)
 {
  return -1;
 }
 for(i = 0; i < length - 1; i++) --------------------------------------->注意条件
 {
  if(array[i] > array[i+1])
  {
   return -1;
  }
 }
 return 0;
}


int binary_search(int array[], int left, int right, int key)
{
 int mid = 0;
 if(right <= 0)
 {
  return -1;
 }
 
 while(left <= right)     --------------------------------------->注意条件
 {
  printf("left = %d, right = %d\n", left, right);
  mid = (left + right) >> 1;                              /*更好的写法是 mid = left + ((right - left) >> 1)*/
  printf("mid = %d, array[mid] = %d\n", mid, array[mid]);
  if(array[mid] < key) 
  {
   left = mid + 1;
  }
  else if(array[mid] > key)
  {
   right = mid - 1;
  } 
  else
  {
   return mid;
  }
 }
 return -1;
}
int main()
{
 int tmp[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
 int num = 0;
 int i = 0;
 int ret = -1;
 printf("tmp array:");
 for(i = 0; i < ARRAY_LEN(tmp); i++)
 {
  printf(" %d", tmp[i]);
 }
 printf("\n");
 if(-1 == is_sort_asc(tmp, ARRAY_LEN(tmp)))
 {
  printf("tmp is not sort by asc\n");
  return -1;
 }

 num = 1;
 ret = binary_search(tmp, 0, ARRAY_LEN(tmp) - 1, num);
 if(-1 == ret)
 {
  printf("can not find the num %d\n", num);
 }
 else
 {
  printf("find key = %d in tmp[%d]\n", num, ret);
 }
 printf("\n");
 return 0;
}

2）二分查找返回key(可能有重复)第一次出现的下标，如无return -1

int binary_search(int array[], int left, int right, int key) 
{ 
    int mid = 0; 
    if(right <= 0) 
    { 
        return -1; 
    } 
     
    while(left <= right) 
    { 
        printf("left = %d, right = %d\n", left, right); 
        mid = (left + right) >> 1; 
        printf("mid = %d, array[mid] = %d\n", mid, array[mid]); 
        if(array[mid] < key)  
        { 
            left = mid + 1; 
        } 
        else if(array[mid] > key) 
        { 
            right = mid - 1; 
        }    
        else 
        { 
            while(mid >= 1) --------------------------->注意条件 
            { 
                if(array[mid] == array[mid-1]) 
                { 
                    mid -= 1; 
                } 
                else 
                { 
                    break; 
                } 
            } 
            return mid; 
        } 
    } 
    return -1; 
} 

int binary_search(int array[], int left, int right, int key)
{
 int mid = 0;
 if(right <= 0)
 {
  return -1;
 }
 
 while(left <= right)
 {
  printf("left = %d, right = %d\n", left, right);
  mid = (left + right) >> 1;
  printf("mid = %d, array[mid] = %d\n", mid, array[mid]);
  if(array[mid] < key) 
  {
   left = mid + 1;
  }
  else if(array[mid] > key)
  {
   right = mid - 1;
  } 
  else
  {
   while(mid >= 1) --------------------------->注意条件
   {
    if(array[mid] == array[mid-1])
    {
     mid -= 1;
    }
    else
    {
     break;
    }
   }
   return mid;
  }
 }
 return -1;
}

4）二分查找返回刚好小于key的元素下标，如无return -1

int binary_search(int array[], int left, int right, int key) 
{ 
    int mid = 0; 
    if(right <= 0) 
    { 
        return -1; 
    } 
     
    while(left <= right) 
    { 
        printf("left = %d, right = %d\n", left, right); 
        mid = (left + right) >> 1; 
        printf("mid = %d, array[mid] = %d\n", mid, array[mid]); 
        if(array[mid] < key)  
        { 
            left = mid + 1; 
        } 
        else if(array[mid] > key) 
        { 
            right = mid - 1; 
        }    
        else 
        { 
            while(mid >= 1) --------------------------->注意条件 
            { 
                if(array[mid] == array[mid-1]) 
                { 
                    mid -= 1; 
                } 
                else 
                { 
                    break; 
                } 
            } 
            return mid - 1; /*查找到是第一个元素 直接找不到小于它的索引*/ 
        } 
    } 
    return -1; 
} 

int binary_search(int array[], int left, int right, int key)
{
 int mid = 0;
 if(right <= 0)
 {
  return -1;
 }
 
 while(left <= right)
 {
  printf("left = %d, right = %d\n", left, right);
  mid = (left + right) >> 1;
  printf("mid = %d, array[mid] = %d\n", mid, array[mid]);
  if(array[mid] < key) 
  {
   left = mid + 1;
  }
  else if(array[mid] > key)
  {
   right = mid - 1;
  } 
  else
  {
   while(mid >= 1) --------------------------->注意条件
   {
    if(array[mid] == array[mid-1])
    {
     mid -= 1;
    }
    else
    {
     break;
    }
   }
   return mid - 1; /*查找到是第一个元素 直接找不到小于它的索引*/
  }
 }
 return -1;
}

补充：综合编程 , 其他综合 ,