算法刻意练习之二分查找

古城微笑少年丶 2022-12-08 14:21 220阅读 0赞

## 1 三个前提条件 ##

**1. 目标函数单调性（单调递增或者递减）。二分的数据必须是有序的，这样可以通过它的某些特征排除掉比如说 前半部分 或 后半部分；  
2. 存在上下界（bounded）；  
3. 能够通过索引访问（index accessible)；**

## 2 代码模板 ##

public int binarySearch(int[] array, int target) {
        int left = 0, right = array.length - 1, mid;
        while (left <= right) {
            mid = (right - left) / 2 + left;
    
            if (target == array[mid]) {
                return mid;
            } else if (target < array[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    
        return -1;
    }

## 3 实战 ##

**1. 先写好二分查找模版，把变量全部代入填写好，再写详细逻辑；  
2. 看实际情况 用不用 mid +- 1；  
3. mid = (left + right) / 2 ，在强类型的语言内可能导致数字越界，那么可以采用mid = left + (right - left) / 2；**

## 4 示例 ##

在递增数组里\[10, 14, 19, 26, 27, 31, 33, 35, 42, 44\]，查找：31  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/3f47cd3f65ec4174ab6187059c334164.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/ac24c4fd0b8a401f9c4bd64556514260.png

发表评论取消回复

表情：

评论列表（有 0 条评论，220人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法】数组查找之二分查找

二分查找要求：有序无重复元素题目 [704. 二分查找 - 力扣（LeetCode）][704. _ - _LeetCode]

心已赠人/ 2024年03月27日 12:41/ 0 赞/ 92 阅读

相关简单算法之二分查找

二分查找算法介绍二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键

水深无声/ 2023年10月09日 15:38/ 0 赞/ 69 阅读

相关 Java算法之二分查找

一、二分查找又叫折半查找，查找要求是：待查找的序列是有序的。二、算法说明：每次取中间位置的值与带查找关键字比较，如果中间位置的值比待查找关键字大，则在前半部分循环这个查找

迷南。/ 2023年01月23日 11:50/ 0 赞/ 23 阅读

相关算法刻意练习之字KMP算法

1 特点（1）KMP ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6

痛定思痛。/ 2022年12月21日 14:58/ 0 赞/ 198 阅读

相关算法刻意练习之动态规划

1 特点 1.1 动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构) 1.共性:找到重复子问题； 2.差异性:最优子结构、中途可以淘太欠优解；

我不是女神ヾ/ 2022年12月21日 06:25/ 0 赞/ 215 阅读

相关算法刻意练习之位运算

1 位运算 1.1 为什么需要位运算 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_

╰半橙微兮°/ 2022年12月21日 06:20/ 0 赞/ 227 阅读

相关算法刻意练习之二分查找

1 三个前提条件 1. 目标函数单调性（单调递增或者递减）。二分的数据必须是有序的，这样可以通过它的某些特征排除掉比如说前半部分或后半部分； 2. 存在上下界（

古城微笑少年丶/ 2022年12月08日 14:21/ 0 赞/ 221 阅读

相关算法刻意练习之堆/二叉堆

1 堆 Heap 1.1 特点 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR

梦里梦外;/ 2022年12月06日 15:14/ 0 赞/ 236 阅读

相关算法之二分查找

概念二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到想要查找的元素，或是区间被缩小

柔光的暖阳◎/ 2022年04月17日 03:58/ 0 赞/ 232 阅读

相关算法导论之二分查找

二分查找的前提是要进行查找的序列必须是有序的，这里我们以升序为例。 <table style="width:500px;"> <tbody> <tr> <t

系统管理员/ 2022年03月21日 12:08/ 0 赞/ 313 阅读