【数据结构与算法12】程序员10大算法之二分查找算法

算法分析

二分查找算法的特点：

• 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找；
• 二分查找法的运行时间为对数时间 O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n 步；

假设从[0,99]的队列(100 个数，即 n=100)中寻到目标数 30，则需要查找步数为㏒₂100 , 即最多需要查找 7 次( 2^6 < 100 < 2^7)

案例1

题目：数组 {1,3, 8, 10, 11, 67, 100}，编程实现二分查找， 要求使用递归和非递归两种方式实现

递归方式实现

public class BinarySearchRecursive {
    public static void main(String[] args) {
        int[] arr = {1,3, 8, 10, 11, 67, 100};
        int i = binarySearchRecur(arr, 0,arr.length-1,11);
        System.out.println(i);
    }


    /**
     * 递归方式实现二分查找
     * @param arr 有序数组
     * @param left 左下标
     * @param right 右下标
     * @param target 目标值
     * @return 找到了返回下标，没找到返回 -1
     */
    public static int binarySearchRecur(int[] arr,int left,int right,int target){
        if(left > right){
            return -1;
        }

        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if(target == midVal){
            return mid;
        }
        else if(target > midVal){
            return binarySearchRecur(arr,mid + 1,right,target);
        }
        else{
            return binarySearchRecur(arr,left,mid - 1,target);
        }

    }
}

非递归方式实现

public class BinarySearchNoRecursive {
    public static void main(String[] args) {
        int[] arr = {1,3, 8, 10, 11, 67, 100};
        int i = binarySearch(arr, -100);
        System.out.println(i);
    }

    /**
     * 二分查找非递归实现方法
     * @param arr  有序的数组
     * @param target 查找目标
     * @return 返回查找到的对象下标，没找到返回 -1
     */
    public static int binarySearch(int[] arr,int target){
        int left = 0;
        int right = arr.length - 1;

        while (left <= right){
            int mid = (left + right) / 2;

            if(arr[mid] == target){
                return mid;
            }else if(arr[mid] > target){
                right = mid - 1;
            }else if(arr[mid] < target){
                left = mid + 1;
            }
        }

        return -1;
    }
}

案例2

题目：剑指 Offer II 068. 查找插入位置

给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right){
            int mid = (left + right) / 2;

            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }
        }

        return right + 1;
    }
}

执行结果：