详解二分查找

目录

一.为什么要使用二分查找

二.二分查找的解释

三.代码实现二分查找

代码1：

代码2：

 四.二分查找的提升之数组部分有序

五.总结：

---

一.为什么要使用二分查找

当有一个排好顺序的数组，我们需要知道我们要找的值是否在当前数组中，那么我们就需要自己实现一个查找的方法来进行实现，那么如果我们找的数在最后一个位置n处，假设这个n非常大，那么我们要是一次一次进行比较的话就要比较n次，这样就会显得非常慢，那么有没有一种相较于普通查找速度更快的方法吗，那就是二分查找。

二.二分查找的解释

二分查找：也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

通过上面的概念我们也可以看出，二分查找就相当于将有顺序的线性表分成两半来进行查找，每一次查找都将原来的线性表分成一半，这样就提高了效率。

下面就通过一个例子来进行具体解释什么是二分查找：

 这种查找相对于顺序查找来说比较的次数就少了，如果理解了二分查找的原理，接下来就是代码实现了。

三.代码实现二分查找

之前学习二分查找的时候，每次都以为自己已经完全掌握，但是里面的细节知道现在才弄明白这里代码实现的差别都是于right有关，下面查找一个数是否存在都是以数组来举例说明。

代码1：

当right=arr.length时

要点1：这里控制循环的left<right可以取等号吗，答案是不可以，因为当相等的时候，找的要是数组的最后一个数组，就会发生数组越界异常。

要点2：向左边查找必须right=mid, 如果right=mid-1就会出现存在的元素可能会找不到，在赋值的时候自己可以试一试。

要点3：使用left=mid+1,这里不使用left=mid是因为我们都已经将mid进行比较过了，不需要再参与运算了。

public class Demo{
//二分查找，找到返回索引位置，未找到返回-1
  public static int binarySearch(int[] arr,int key) {
      if(arr.length==0){//数组为空时
            return -1;
         }
    int left = 0;
    int right =arr.length;
    while(left<right){
        int mid = left+((right-left)>>1);//使用右移，因为移位比四则运算快
        if(arr[mid] == key){//相等返回
            return mid;
        }else if(arr[mid]>key){//向左边查找
            right = mid;
        }else if(arr[mid]<key){//向右边查找
            left = mid+1;
        }
    }
    return -1;
    }
    public static void main(String[] args){
      int[] arr = {1,2,3,4,5,6,7,8};
      System.out.println(binarySearch(arr,8));//7
    }
}

代码2：

当right=arr.length-1时

这里所强调的要点与上面的有所不同，主要是由于right不同导致与代码1中的要点1，2不同，具体不同如下所示：

要点1：这里控制循环变为left<=right，因为right所代表的位置参与之中的计算。

要点2：向左边查找必须right=mid-1, 因为mid-1的位置可以访问到，mid的位置的元素已经比较过了。

要点3：使用left=mid+1,这里不使用left=mid是因为我们都已经将mid进行比较过了，不需要再参与运算了。

public class Demo{
//二分查找，找到返回索引位置，未找到返回-1
         public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left<=right) {
            int mid = left+((right-left)>>1);
            if(nums[mid] == target) {
                return mid;
            } else if(nums[0]<nums[mid]) {
                //说明（0，mid）有序
                //接着判断查找值是否在有序区间，如果不在，就向后查找，存在就向左查找
                if(nums[mid]>target && nums[0]<=target) {
                    right = mid-1;
                }else {
                    left = mid+1;
                }
            }else {
                //（mid，nums.length有序）,在有序的区间的内进行二分查找
                if(nums[mid]<target && nums[right]>=target) {
                    left = mid+1;
                }else {
                    right = mid-1;
                }
            }
        }
        //表明没有找到
        return -1;
    }
}

运行结果：

 这两种代码结果都相同，除了里面的具体实现有所差别。

 四.二分查找的提升之数组部分有序

对于二分查找来说，需要的数组是有序的，但是对于一个经过某个元素旋转之后的数组也是可以使用二分查找，例如下面的数组：

int[] arr1 = {6,7,8,1,2,3,4,5};

int[] arr2 = {4，5，6,7,8,1,2,3};

 

 对于这种旋转后的数组无非就是对应了两种情况，要么就是mid比left小，要么就是mid比left大，通过这两种不同我们将之前的代码进行再判断是否向左还是向右查找需要进行修改一下，其他的思路基本不变，再这里我们使用代码2中的right=arr.length-1方法来进行实现。

代码如下：

public class Demo{
public class Demo{
//二分查找，找到返回索引位置，未找到返回-1
         public static int binarySearch(int[] arr,int key){
         if(arr.length==0){//数组为空时
            return -1;
         }
        int left = 0;
        int right = arr.length-1;
        while(left<=right){
            int mid = left+((right-left)>>1);
            if(arr[mid]==key){
                return mid;
            }else if(arr[mid]>key){//向左找
                right = mid-1;
            }else if(arr[mid]<key){//向右找
                left = mid+1;
            }
        }
        return -1;
    }
    public static void main(String[] args){
      int[] arr = {1,2,3,4,5,6,7,8};
      System.out.println(binarySearch(arr,8));//7
    }
}
    public static void main(String[] args){
        int[] arr1 = {6,7,8,1,2,3,4,5};
        int[] arr2 = {4,5,6,7,8,1,2,3};
        System.out.println(partBinarySearch(arr1,4));//6
        System.out.println(partBinarySearch(arr2,4));//0
    }
}

运行结果：

五.总结：

对于二分查找，应该明确每次二分后应该从哪边开始查找，然后要注意边界问题，找到后进行返回查询的结果，如果这些问题都理解了，二分查找应该也没有问题了。