今天会是有Offer的一天么：面试时你真的会写二分查找吗？
2020-04-20 本文已影响0人
4d11ff5df74e
二分查找是一种非常常见的算法，在面试时会经常被问到。其输入是一个有序的数组，输出需要查找数字的下标（注意输入一定是有序的）。
image
先说一下最基本的，有序数组中没有重复的元素。
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;
}
}
image
image
接着说一下二分查找的变种，比如说对于一个有序数组中，可以存在重复的元素。
查找第一个与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;
}
}
咱们接着说一下另外几种变种
image
查找第一个大于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;
}
}
image
查找最后一个小于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;
}
}
image
最后两种变种
查找第一个等于或者大于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;
}
}
image
查找最后一个小于或等于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;
}
}
image
二分查找的变化还是比较多的，但原理基本上都一样。掌握最基本的一种后，对于其他的，再写的时候要好好想一下它们的判断条件和边界。总之，二分查找是我们最应该掌握的一种查找算法**
转载于：https://blog.csdn.net/HZGuilty/article/details/105600914
