能不能拿下大厂Offer？看你面试时会不会写二分查找

二分查找是一种非常常见的算法，在面试时会经常被问到。其输入是一个有序的数组，输出需要查找数字的下标（注意输入一定是有序的）。

先说一下最基本的，有序数组中没有重复的元素。

public class binarySearchTest

{

public static void main(String[] args)

{

int[] num = new int[]

{

1, 4, 6, 7, 9, 10, 14, 18, 19, 27, 30

}; ///初始数组一定是有序的

int key = 27;

System.out.println("初始数组为：");

for(int i = 0; i < num.length; i++)

{

System.out.print(num[i] + " ");

}

System.out.println();

System.out.println("要查找的数字：" + key);

binarySearch(num, key);

}

public static int binarySearch(int[] num, int key)

{

int left = 0;

int right = num.length - 1;

///这里一定要注意是left<=right

while(left <= right)

{

int middle = (left + right) / 2;

System.out.println("left=" + num[left] + "  right=" + num[right] + "  middle=" + num[middle]);

if(num[middle] == key)

{

System.out.println("查找成功");

return middle;

}

else if(num[middle] < key)

{

left = middle + 1;

}

else

{

right = middle - 1;

}

}

System.out.println("查找失败");

return -1;

}

}

}

接着说一下二分查找的变种，比如说对于一个有序数组中，可以存在重复的元素。

查找第一个与key相同的数字的下标

public class binarySearchTest

{

public static void main(String[] args)

{

int[] num = new int[]

{

1, 4, 4, 4, 6, 7, 9, 10, 14, 18, 19, 27, 30

}; ///初始数组一定是有序的

int key = 4;

System.out.println("初始数组为：");

for(int i = 0; i < num.length; i++)

{

System.out.print(num[i] + " ");

}

System.out.println();

System.out.println("要查找的数字：" + key);

binarySearch(num, key);

}

public static int binarySearch(int[] num, int key)

{

int left = 0;

int right = num.length - 1;

///这里一定要注意是left<=right

while(left <= right)

{

int middle = (left + right) / 2;

System.out.println("left=" + num[left] + "  right=" + num[right] + "  middle=" + num[middle]);

if(num[middle] >= key)

{

right = middle - 1;

}

else

{

left = middle + 1;

}

}

System.out.println("最后一次查询： " + "left=" + num[left] + "  right=" + num[right]);

//这里需要判断一下num[left]是否等于key

if(left < num.length && num[left] == key)

{

System.out.println("查找成功");

return left;

}

System.out.println("查找失败");

return -1;

}

查找最后一个与key相等数字的下标

public class binarySearchTest

{

public static void main(String[] args)

{

int[] num = new int[]

{

1, 4, 6, 7, 9, 10, 10, 10, 10, 14, 18, 19, 27, 30

}; ///初始数组一定是有序的

int key = 10;

System.out.println("初始数组为：");

for(int i = 0; i < num.length; i++)

{

System.out.print(num[i] + " ");

}

System.out.println();

System.out.println("要查找的数字：" + key);

binarySearch(num, key);

}

public static int binarySearch(int[] num, int key)

{

int left = 0;

int right = num.length - 1;

///这里一定要注意是left<=right

while(left <= right)

{

int middle = (left + right) / 2;

System.out.println("left=" + num[left] + "  right=" + num[right] + "  middle=" + num[middle]);

if(num[middle] > key)

{

right = middle - 1;

}

else

{

left = middle + 1;

}

}

System.out.println("最后一次查询： " + "left=" + num[left] + "  right=" + num[right]);

//这里需要判断一下num[left]是否等于key

if(right >= 0 && num[right] == key)

{

System.out.println("查找成功");

return right;

}

System.out.println("查找失败");

return -1;

}

}

咱们接着说一下另外几种变种

查找第一个大于key的数字的下标

public class binarySearchTest

{

public static void main(String[] args)

{

int[] num = new int[]

{

1, 4, 4, 4, 6, 7, 9, 10, 14, 18, 19, 27, 30

}; ///初始数组一定是有序的

int key = 4;

System.out.println("初始数组为：");

for(int i = 0; i < num.length; i++)

{

System.out.print(num[i] + " ");

}

System.out.println();

System.out.println("要查找第一个大于：" + key + "的数字");

binarySearch(num, key);

}

public static int binarySearch(int[] num, int key)

{

int left = 0;

int right = num.length - 1;

///这里一定要注意是left<=right

while(left <= right)

{

int middle = (left + right) / 2;

System.out.println("left=" + num[left] + "  right=" + num[right] + "  middle=" + num[middle]);

if(num[middle] > key)

{

right = middle - 1;

}

else

{

left = middle + 1;

}

}

System.out.println("最后一次查询： " + "left=" + num[left] + "  right=" + num[right]);

//这里需要判断一下left是否小于num.length

if(left < num.length)

{

System.out.println("查找成功");

return left;

}

System.out.println("查找失败");

return -1;

}

}

查找最后一个小于key的数字的下标

public class binarySearchTest

{

public static void main(String[] args)

{

int[] num = new int[]

{

1, 4, 4, 4, 6, 7, 9, 10, 14, 18, 19, 27, 30

}; ///初始数组一定是有序的

int key = 18;

System.out.println("初始数组为：");

for(int i = 0; i < num.length; i++)

{

System.out.print(num[i] + " ");

}

System.out.println();

System.out.println("要查找最后一个小于：" + key + "的数字");

binarySearch(num, key);

}

public static int binarySearch(int[] num, int key)

{

int left = 0;

int right = num.length - 1;

///这里一定要注意是left<=right

while(left <= right)

{

int middle = (left + right) / 2;

System.out.println("left=" + num[left] + "  right=" + num[right] + "  middle=" + num[middle]);

if(num[middle] >= key)

{

right = middle - 1;

}

else

{

left = middle + 1;

}

}

System.out.println("最后一次查询： " + "left=" + num[left] + "  right=" + num[right]);

//这里需要判断一下right是否大于等于0

if(right >= 0)

{

System.out.println("查找成功");

return right;

}

System.out.println("查找失败");

return -1;

}

}

最后两种变种

查找第一个等于或者大于key数字的下标

public class binarySearchTest

{

public static void main(String[] args)

{

int[] num = new int[]

{

1, 4, 4, 4, 6, 7, 9, 10, 14, 18, 19, 27, 30

}; ///初始数组一定是有序的

int key = 8;

System.out.println("初始数组为：");

for(int i = 0; i < num.length; i++)

{

System.out.print(num[i] + " ");

}

System.out.println();

System.out.println("要查找第一个等于或者大于：" + key + "的数字");

binarySearch(num, key);

}

public static int binarySearch(int[] num, int key)

{

int left = 0;

int right = num.length - 1;

///这里一定要注意是left<=right

while(left <= right)

{

int middle = (left + right) / 2;

System.out.println("left=" + num[left] + "  right=" + num[right] + "  middle=" + num[middle]);

if(num[middle] >= key)

{

right = middle - 1;

}

else

{

left = middle + 1;

}

}

System.out.println("最后一次查询： " + "left=" + num[left] + "  right=" + num[right]);

//这里需要判断一下

if(left <= num.length)

{

System.out.println("查找成功");

return left;

}

System.out.println("查找失败");

return -1;

}

}

查找最后一个小于或等于key数字的下标

public class binarySearchTest

{

public static void main(String[] args)

{

int[] num = new int[]

{

1, 4, 4, 4, 6, 7, 9, 10, 14, 18, 19, 27, 30

}; ///初始数组一定是有序的

int key = 8;

System.out.println("初始数组为：");

for(int i = 0; i < num.length; i++)

{

System.out.print(num[i] + " ");

}

System.out.println();

System.out.println("要查找最后一个小于或等于：" + key + "的数字");

binarySearch(num, key);

}

public static int binarySearch(int[] num, int key)

{

int left = 0;

int right = num.length - 1;

///这里一定要注意是left<=right

while(left <= right)

{

int middle = (left + right) / 2;

System.out.println("left=" + num[left] + "  right=" + num[right] + "  middle=" + num[middle]);

if(num[middle] > key)

{

right = middle - 1;

}

else

{

left = middle + 1;

}

}

System.out.println("最后一次查询： " + "left=" + num[left] + "  right=" + num[right]);

//这里需要判断一下

if(right >= 0)

{

System.out.println("查找成功");

return right;

}

System.out.println("查找失败");

return -1;

}

}

二分查找的变化还是被较多的，但原理基本上都一样。掌握最基本的一种后，对于其他的，再写的时候要好好想一下他们的判断条件和边界。总之二分查找是我们最因该掌握的一种查找算法。

原文链接：https://blog.csdn.net/HZGuilty/article/details/105600914