二分查找

简介

介绍

二分查找（Binary Search），也称为折半查找，是一种高效的查找算法，用于在有序数组或列表中查找特定元素的位置或判断其是否存在。它是一种简单而高效的查找算法，可以在大规模数据集上提供快速搜索和定位的能力。

基本思想

二分查找的基本思想是通过不断缩小搜索范围来逼近目标元素。

核心步骤

1. 将目标元素与有序数组或列表的中间元素进行比较
2. 如果目标元素等于中间元素，则找到了目标元素，返回其位置
3. 如果目标元素小于中间元素，则在数组或列表的左半部分继续进行二分查找
4. 如果目标元素大于中间元素，则在数组或列表的右半部分继续进行二分查找
5. 重复上述步骤，不断缩小搜索范围，直到找到目标元素或确定目标元素不存在

限制条件

数组或列表必须是有序的。

数组或列表没有重复元素。

二分查找适用于静态数据集，即不会频繁插入或删除元素的情况。

对于链表等非连续存储结构，无法直接使用二分查找。

用处

在有序数组中查找特定元素、确定元素的插入位置、查找出现次数等。

基本信息

输入：一个整数数组，一个目标值

输出：目标值在整数数组中的下标

使用前提：数组要是有序数组且不重复

空间复杂度：O(1)

时间复杂度：O(log n)

代码实现

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 left = mid + 1;
    }
    return -1;
}

另外可以调用API实现

int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,34,234};
int target = 8;
int res = Arrays.binarySearch(arr,target);
System.out.println(res);

例题

x的平方根

来源

例题链接：69 - x 的平方根(LeetCode)

题解

由于x平方根的整数部分ans满足

$$k^{2}\leq x$$

的最大K值，因此我们可以对K进行二分查找

代码

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}