二分查找算法是在有序数组中用到较为频繁的一种算法。如果不使用二分算法直接对数组进行遍历，跟每个元素进行比较，其时间复杂度为O(n)。

 

 

但是二分查找算法则更优，因为其查找的时间复杂度为O(lgn)，比如数组{1,2,3,4,5,6,7,8,9}。需要查找元素，用二分查找的算法执行的话，其顺序为：

第一步：查找中间元素，即为5。由于5<6，则6必然在5之后的数组元素中，那么就在{6,7,8,9}查找；

第二步：寻找{6,7,8,9}的中位数，选7。由于7>6，则6应该在7左边的数组元素中，那么只剩下6，即找到了。

 

 

说白了二分查找法就是不断将数组进行对半分割，每次拿中间元素和目标值进行比较。

 

案例一：

package cn.imooc.java2;public class Test02 {     //定义一个静态方法     static int binarySerach(int[] array, int key) {          //定义数组下标的最左         int left = 0;         //定义数组下标的最右（下标都是从0开始的，因此需要-1）         int right = array.length - 1;         while (left <= right) {             int mid = (left + right) / 2;             //判断中间值是否为目标值             if (array[mid] == key) {                 return mid;             }             else if (array[mid] < key) {                 left = mid + 1;             }             else {                 right = mid - 1;             }         }         return -1;     }    //测试，目标值为7     public static void main(String[] args) {          Test02 s = new Test02();          int[] b={1,5,6,7,8,9,10,12};                System.out.println(s.binarySerach(b, 7));     }}

注意：每次移动left和right指针的时候，需要在mid的基础上+1或者-1， 防止出现死循环， 程序也就能够正确的运行。并且代码中的判断条件必须是while (left <= right)，否则的话判断条件不完整，比如：array[3] = {1, 3, 5};待查找的键为5，此时在(low < high)条件下就会找不到，因为low和high相等时，指向元素5，但是此时条件不成立，没有进入while()中。

 

 

案例二：查找第一个相等的元素

package cn.imooc.java2;public class Test02 {     // 查找第一个相等的元素     static int findFirstEqual(int[] array, int key) {         int left = 0;         int right = array.length - 1;         while (left <= right) {             int mid = (left + right) / 2;             if (array[mid] >= key) {                 right = mid - 1;             }             else {                 left = mid + 1;             }         }         if (left < array.length && array[left] == key) {             return left;         }                 return -1;     }     public static void main(String[] args) {          Test02 s = new Test02();          int[] b={1,5,6,7,7,7,7,8,9,10,12};                   System.out.println(s.findFirstEqual(b, 7));     }}

　　

案例三：查找最后一个相等的元素

package cn.imooc.java2;public class Test02 {     static int findLastEqual(int[] array, int key) {         int left = 0;         int right = array.length - 1;         while (left <= right) {             int mid = (left + right) / 2;             if (array[mid] <= key) {                 left = mid + 1;             }             else {                 right = mid - 1;             }         }         if (right >= 0 && array[right] == key) {             return right;         }         return -1;     }     public static void main(String[] args) {          Test02 s = new Test02();          int[] b={1,5,6,7,7,7,7,8,9,10,12};                   System.out.println(s.findLastEqual(b, 7));     }}

　　

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

package cn.imooc.java2;public class Test02 {     static int findLastEqualSmaller(int[] array, int key) {         int left = 0;         int right = array.length - 1;         while (left <= right) {             int mid = (left + right) / 2;             if (array[mid] > key) {                 right = mid - 1;             }             else {                 left = mid + 1;             }         }         return right;     }     public static void main(String[] args) {          Test02 s = new Test02();          int[] b={
    1,5,6,7,7,7,7,8,9,10,12};                   System.out.println(s.findLastEqualSmaller(b, 11));     }}

 

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

package cn.imooc.java2;public class Test02 {     static int findFirstEqualLarger(int[] array, int key) {         int left = 0;         int right = array.length - 1;         while (left <= right) {             int mid = (left + right) / 2;             if (array[mid] >= key) {                 right = mid - 1;             }             else {                 left = mid + 1;             }         }         return left;     }     public static void main(String[] args) {          Test02 s = new Test02();          int[] b={1,5,6,7,7,7,7,8,9,10,12};                   System.out.println(s.findFirstEqualLarger(b, 11));     }}

　　

案例六：查找第一个大于key的元素，也就是说返回大于key的最左边元素下标。

package cn.imooc.java2;public class Test02 {     static int findFirstLarger(int[] array, int key) {         int left = 0;         int right = array.length - 1;         while (left <= right) {             int mid = (left + right) / 2;             if (array[mid] > key) {                 right = mid - 1;             }             else {                 left = mid + 1;             }         }         return left;     }     public static void main(String[] args) {          Test02 s = new Test02();          int[] b={1,5,6,7,7,7,7,8,9,10,12};                   System.out.println(s.findFirstLarger(b, 11));     }}