算法刻意练习之二分查找

古城微笑少年丶 2022-12-08 14:21 190阅读 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