二分查找算法是在有序数组中用到较为频繁的一种算法。如果不使用二分算法直接对数组进行遍历，跟每个元素进行比较，其时间复杂度为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));
}
}