21天经典算法之折半查找

​
​

活动地址：CSDN21天学习挑战赛

专栏前言:

本专栏主要是算法训练，目的很简单。就是为了进厂
最近官方在组织 21 天挑战赛，趁此机会我也更新一下经典算法的文章
如果想一起“狂”或者交流，欢迎来私聊
还不快趁着这个机会来提升自己💪

👉查找算法介绍

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算。

之前讲过顺序查找链接直达。现在就来讲讲折半查找是怎么一回事。

👉折半查找

原理

折半查找也叫做二分查找，是在一种有序数组中查找某一个特定元素的查找算法。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且和开始一样从中间元素开始比较。如此反复知道找到该元素位置或者确定表中没有所需要的元素，则证明查找失败。如果在某一步骤数组为空，则代表找不到。

折半查找，仅适用于有序的顺序表

代码实现

有序数组：nums[]
目标值：target

int left = 0, 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度分析

折半查找需要方便地定位查找区域，所以适合折半查找的存储结构必须具有随机存取的特性。因此，该查找法仅适合于线性表的顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列。

时间复杂度：

• 最好的情况：$O(1)$。第一次比较的时候就找到了该元素。
• 最坏的情况：$O(lo{g}_{2}n)$。循环次数和n有关。每次都会折半。
• 平均复杂度：$O(lo{g}_{2}n)$。

空间复杂度：$O(1)$。仅需若干个额外存储空间用于记录，即空间复杂度为 $O(1)$。

👉示例：

👉算法实践

💭
算法的整体思想已经在上面讲述了，下面直接使用一个例子来试试水。

折半查找

运用了折半查找，并在此基础上加入了其他要求。

剑指 Offer 53 - I. 在排序数组中查找数字 I

题目描述：

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
1
2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
1
2

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

解题：

class Solution {
    public int search(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return rightIdx - leftIdx + 1;
        } 
        return 0;
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

👉课后习题

如果你觉得掌握了，那么赶快来实践一下吧

​