1.二分查找算法详解

• 算法定义

二分查找算法又叫折半查找算法, 是一种基于比较目标值和数组中间元素的教科书式算

• 使用条件

待查找的数组必须是有顺序的

• 算法规则

1.如果目标值等于中间元素，则找到目标值。
2.如果目标值较小，继续在左侧搜索。
3.如果目标值较大，则继续在右侧搜索。

•  算法分析

1.初始化指针 left = 0, right = n - 1。 
2.当 left <= right： 
3.比较中间元素 nums[pivot] 和目标值 target 。 
如果 target = nums[pivot]，返回 pivot。 
如果 target < nums[pivot]，则在左侧继续搜索 right = pivot - 1。 
如果 target > nums[pivot]，则在右侧继续搜索 left = pivot + 1。

2.代码示例

/**
 * @author 民宿
 * @dscription 二分查找算法
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 46, 66, 91, 91, 99};
        int target = 33;
        // boolean isExit = binarySearch(arr, 0, arr.length - 1, target);
        boolean isExit = binarySearch(arr, target);
        if (isExit) {
            System.out.println("success！");
        } else {
            System.out.println("fail!");
        }
    }

    /**
     * 循环遍历方式查询数组中目标值是否存在
     *
     * @param arr 有序数组
     * @param target 目标值
     * @return
     */
    private static boolean binarySearch(int[] arr, int target) {
        int beginIndex = 0;
        int endIndex = arr.length - 1;
        int middle = (beginIndex + endIndex) / 2;

        while (beginIndex <= endIndex) {
            if (arr[middle] < target) {
                beginIndex = middle + 1;
                middle = (beginIndex + endIndex) / 2;
            } else if (arr[middle] > target) {
                endIndex = middle - 1;
                middle = (beginIndex + endIndex) / 2;
            } else {
                return true;
            }
        }

        return false;
    }

    /**
     * 递归方式查找数组中目标值是否存在
     *
     * @param arr        有序数组
     * @param beginIndex 起始索引
     * @param endIndex   结束索引
     * @param target     目标值
     * @return
     */
    private static boolean binarySearch(int[] arr, int beginIndex, int endIndex, int target) {
        if (beginIndex > endIndex) {
            return false;
        }

        int middle = (beginIndex + endIndex) / 2;
        if (arr[middle] < target) {
            return binarySearch(arr, middle + 1, endIndex, target);
        } else if (arr[middle] > target) {
            return binarySearch(arr, beginIndex, middle - 1, target);
        } else {
            return true;
        }
    }
}

LeetCode官方解法

class Solution {
  public int search(int[] nums, int target) {
    int pivot, left = 0, right = nums.length - 1;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (nums[pivot] == target) return pivot;
      if (target < nums[pivot]) right = pivot - 1;
      else left = pivot + 1;
    }
    return -1;
  }
}

3.算法复杂度

4.二分查找算法最佳Solution

有一天阿东到图书馆借了 N本书，出图书馆的时候，警报响了，于是保安把阿东拦下，要检查一下哪本书没有登记出借。阿东正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆……
最终，检测了 logN 次之后，保安成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是阿东背着剩下的书走了。
从此，图书馆丢了 N - 1 本书。

事故现场还原：

数组下标:0 1 2 3 4 
存储内容:1 2 2 2 3

比如说给你有序数组 nums = [1,2,2,2,3]，target 为 2，上面算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。

解决上述需求，完整算法如下:

基础二分法算法

//和官方的Leetcode 算法一致
//基础二分查找算法
int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

左侧边界二分法算法如下

//左侧边界查找算法
int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，收缩左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target){
        return -1;
    }
    return left;
}

右侧边界二分法算法如下

//右侧边界查询算法
int rightBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，收缩右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target){
        return -1;
    }
    return right;
}