​
​

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

怕什么真理无穷，进一步有一份的欢喜。

【21天学习挑战赛】折半查找

我为什么参与挑战赛

1，机缘

读到研一了，暑假假期打开私信发现这个挑战赛就鼓起勇气参加了。

2，期待的收获

A, 本人在华南理工大学攻读专硕，目前研究方向是图像恢复，从事深度学习相关工作，目标是从事Java后端开发。
B, 期待您的反馈，如果有什么不对的地方，欢迎指正！
C, 期待认识志同道合的领域同行或技术交流。
如果感觉博主的文章还不错的话，还请关注、点赞、收藏三连支持一下博主哦

什么是折半查找？

折半查找的又称为二分查找，是一种效率相对较高的查找方法。使用该算法的前提要求是元素已经有序，如同名字一样，每次都是根据区间中心将元素分为左右半边，通过比较区间中心和要查找的元素的值，确定下次要查左半边还是右半边。

折半查找的优劣

优势

时间复杂度为O(log2n)，查找的速度较快，并且比较简单实现，通过判断来不断更新区间的左右端点值。

劣势

要求元素已经有序，这在大多数情况下不存在，且插入删除困难。

折半查找的步骤

不断的重复取中间比较和指定新的搜索区间这两个步骤，直到区间左右端点重合(代表搜素结束)或者找到元素为止。

1. 与key相同：直接返回对应的位置
2. 与key大：由于元素有序，要查找的元素一定在左侧(如有)，于是搜素区间变为左一半
3. 与key小：由于元素有序，要查找的元素一定在右侧(如有)，于是搜素区间变为右一半

️ 算法实现

public class BinarySearch {
    

    public static void main(String[] args) {
    
        // input data
        int[] a = {
    10, 11, 12, 14, 20, 32, 34, 35, 41, 43};
        int key = 11;
        // 调用算法，并输出结果
        int result = search(a, key);
        System.out.println(result);
    }

    private static int search(int[] nums, int target) {
    
        // 初始化变量
        int left = 0, right = nums.length - 1, mid = 0;
        // 循环终止条件为：左右端点发生交错
        while (left <= right) {
    
            mid = (left + right) >> 1;//除以2
            if (nums[mid] == target) {
    
                return mid;
            } else if (nums[mid] < target) {
    
                left = mid + 1;
            } else if (nums[mid] > target) {
    
                right = mid - 1;
            }
        }
        // 循环结束还未触发内部的return则代表未找到，此时返回-1
        return -1;
    }

}

相关题目

搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104
作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/array-and-string/cxqdh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

答案
使用折半查找

class Solution {
    
    public int searchInsert(int[] nums, int target) {
    
        // 折半查找
        int left = 0, right = nums.length - 1, mid = 0;
        while (left <= right) {
    
            // 防止 left+right 整型溢出
            mid = (left + right) >> 1;
            if (nums[mid] == target) {
    
                return mid;
            } else if (nums[mid] < target) {
    
                left = mid + 1;
            } else if (nums[mid] > target) {
    
                right = mid - 1;
            }
        }
        return left;
    }
}

如果觉得对你有帮助的话:
点赞，你的认可是我创作的动力！
️ 收藏，你的青睐是我努力的方向！
️ 评论，你的意见是我进步的财富！

​​