二分查找在面试中经常被问到，尤其是他的各种变化版本。二分查找就是把查找的键值和子数组中的中间键作比较，如果被找的键值小于中间键，则在左半部分继续查找；如果大于中间值就在右半部分查找；否则就是要查找的元素。

基本二分查找

　　给定一个有序数组和一个关键字，找到该值在数组中的下标，否则返回-1

1 int BinarySearch(int a[],int size,int key) 2 { 3     int left = 0, right = size - 1; 4     while (left <= right) 5     { 6         int mid = left + (right - left) / 2; 7         if (a[mid] == key) return mid; 8         else if (a[mid] < key) left = mid + 1; 9         else right = mid - 1;10     }11     return -1;12 }

二分查找变种

　　一、查找第一个与key相等的元素，也就是说等于查找key值的元素有很多，返回这些元素最左边的元素的下标。

1 //查找第一个与key相等的元素 2 int BinarySearch(int a[],int size,int key) 3 { 4     int left = 0, right = size - 1; 5     while (left <= right) 6     { 7         int mid = left + (right - left) / 2; 8         if (a[mid] >= key) right = mid - 1; 9         else left = mid + 1;10     }11     if (left < size&&a[left] == key)12     {13         return left;14     }15     return -1;16 }

　　二、查找最后一个与key相等的元素，也就是等于查找key值的元素有好多个，返回这些元素最右边元素的下标。

1 //查找最后一个与key相等的元素 2 int BinarySearch(int a[],int size,int key) 3 { 4     int left = 0, right = size - 1; 5     while (left <= right) 6     { 7         int mid = left + (right - left) / 2; 8         if (a[mid] <= key) left = mid + 1; 9         else right = mid - 1;10     }11     if (right >=0 && a[right] == key)12     {13         return right;14     }15     return -1;16 }

　　三、查找第一个等于或者大于key的元素，查找第一个等于或者大于key的元素，也就是说查找key值的元素有好多个，返回这些元素最左边元素的下标；如果没有等于key值的元素，则返回大于key的最左边元素的下标。

1 //查找第一个等于或者大于key的元素 2 int BinarySearch(int a[],int size,int key) 3 { 4     //如果a[right]
     
      = key) right = mid - 1;11         else left = mid + 1;12     }13     return left;14 }
     

　　四、查找第一个大于key的元素。查找第一个大于key的值，也就是说返回大于key的最左边元素的下标。

1 //查找第一个大于key的元素 2 int BinarySearch(int a[],int size,int key) 3 { 4     //如果a[right]<=key,则找不到大于key的值，直接返回-1 5     int left = 0, right = size - 1; 6     if (a[right] <= key) return -1; 7     while (left <= right) 8     { 9         int mid = left + (right - left) / 2;10         if (a[mid] > key) right = mid - 1;11         else left = mid + 1;12     }13     return left;14 }

　　五、查找最后一个等于或者小于key的元素。查找最后一个等于或者小于key的元素，也就是说等于查找key值有很多，返回这些元素最右边的元素的下标；如果没有等于key值的元素，则返回小于key值的最右边元素的下标。

1 //查找最后一个等于或者小于key的元素 2 int BinarySearch(int a[],int size,int key) 3 { 4     //如果a[left]>key,则找不到等于或者小于key的值，直接返回-1 5     int left = 0, right = size - 1; 6     if (a[left]>key) return -1; 7     while (left <= right) 8     { 9         int mid = left + (right - left) / 2;10         if (a[mid] > key) right = mid - 1;11         else left = mid + 1;12     }13     return right;14 }

　　六、查找最后一个小于key的元素。查找最后一个小于key的元素，也就是说返回小于key的最右边的元素下标。

1 //查找最后一个小于key的元素 2 int BinarySearch(int a[],int size,int key) 3 { 4     //如果a[left]>=key,则找不到=小于key的值，直接返回-1 5     int left = 0, right = size - 1; 6     if (a[left]>=key) return -1; 7     while (left <= right) 8     { 9         int mid = left + (right - left) / 2;10         if (a[mid] >= key) right = mid - 1;11         else left = mid + 1;12     }13     return right;14 }

 

二分查找总结：

　　二分查找的步骤：

1、首先判断出返回的是left还是right。因为我们知道最后跳出while（left<=right）循环条件是right<left并且right=left-1.最后right和left一定是卡在“边界值”的左右两边，如果是比较值为key，查找大于等于key的元素，则边界值就是等于key的所有元素的最左边那个，其实应该返回left。

2、判断比较符号