【算法】二分查找

梦里梦外; 2022-04-22 12:26 286阅读 0赞

# 前言 #

Github：[https://github.com/yihonglei/road-of-arch][https_github.com_yihonglei_road-of-arch]（thinking-in-algorithms）

# 目录 #

二分法查找

二分查找变种1：查找第一个值等于给定值的元素。

二分查找变种2：查找最后一个值等于给定值的元素。

二分查找变种3：查找第一个值大于等于给定值的元素。

二分查找变种4：查找最后一个值小于等于给定值的元素。

--------------------

# 二分法查找 #

二分法在数组中查找目标元素。

package com.jpeony.algorithm.binarysearch;
    
    /**
     * 简单二分查找算法
     *
     * @author yihonglei
     */
    public class BinarySearch {
        public static void main(String[] args) {
            // 查找数组
            int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
            // 目标元素
            int target = 4;
            // 目标元素下标位置，默认-1
            int index = -1;
            // 低位
            int low = 0;
            // 高位
            int high = arr.length - 1;
    
            // 查找目标元素下标
            while (low <= high) {
                // 中位
                int mid = (low + high) / 2;
                // 中间位置为目标元素
                if (arr[mid] == target) {
                    index = mid;
                    break;
                }
                // 如果中间元素大于目标元素，说明要查找的元素在数组的左边范围，缩小查找范围，高位变为mid - 1，继续查找
                if (arr[mid] > target) {
                    high = mid - 1;
                } else if (arr[mid] < target) {
                    // 如果中间元素小于目标元素，说明要查找的元素在数组的右边范围，缩小查找范围，低位变为mid + 1，，继续查找
                    low = mid + 1;
                }
            }
    
            // 结果输出
            if (index >= 0) {
                System.out.println("target-index = " + index + ", target-value = " + arr[index]);
            } else {
                System.out.println("Target element not found");
            }
        }
    }

**使用前提：**

该算法的使用前提必须基于有序表使用。

**算法思想：**

因为数组元素是有序的，每次查找从中间分段，比较中间元素是否是目标元素，

如果不是，则根据目标元素与中间元素比较结果，看是基于前半段查找还是后半段查找。

不断重复此过程，直到找到目标元素为止。

**算法优点：**

查找效率高，不需要像线性查找一样挨个元素比较，二分查找能减少比较次数。

**算法缺点：**

应用面比较窄，因为要基于有序表才能使用二分查找。

# 二分查找变种1：查找第一个值等于给定值的元素。 #

package com.jpeony.algorithm.binarysearch;
    
    /**
     * 【变体1】：查找第一个值等于给定值的元素
     *
     * @author yihonglei
     */
    public class SearchFirstEqualsTarget {
        public static void main(String[] args) {
            // 查找数组
            int[] arr = {1, 2, 3, 3, 3, 3, 4, 5, 6, 7, 8, 9};
            // 目标元素
            int target = 3;
            // 目标元素的下标位置，默认-1
            int index = -1;
            // 低位
            int low = 0;
            // 高位
            int high = arr.length - 1;
    
            // 查找第一个值等于给定值的元素
            while (low <= high) {
                // 中位
                int mid = (low + high) / 2;
                // 如果中间元素大于目标元素，说明查找的元素在数组左边范围，缩小查找范围，高位变为 high = mid - 1，继续查找
                if (arr[mid] > target) {
                    high = mid - 1;
                } else if (arr[mid] < target) {
                    // 如果中间元素小于目标元素，说明查找的元素在数组右边范围，缩小查找范围，地位变为 low = mid + 1，继续查找
                    low = mid + 1;
                } else if (arr[mid] == target) {// 查找到目标元素，需要继续往前查找第一个等于目标元素的元素
                    // 第一位元素等于目标元素 或 目标元素的前一个元素已经不是目标值，则当前位元素就是第一个等于目标元素的值
                    if (mid == 0 || arr[mid - 1] != target) {
                        index = mid;
                        break;
                    } else {
                        // 继续进行二分查找第一个等于目标值的元素，继续查找
                        high = mid - 1;
                    }
                }
            }
    
            // 结果输出
            if (index >= 0) {
                System.out.println("target-index = " + index + ", target-value = " + arr[index]);
            } else {
                System.out.println("Target element not found");
            }
        }
    }

# 二分查找变种2：查找最后一个值等于给定值的元素。 #

package com.jpeony.algorithm.binarysearch;
    
    /**
     * 【变体2】：查找最后一个值等于给定值的元素
     *
     * @author yihonglei
     */
    public class SearchLastEqualsTarget {
        public static void main(String[] args) {
            // 查找数组
            int[] arr = {1, 2, 3, 3, 3, 3, 4, 5, 6, 7, 8, 9};
            // 目标元素
            int target = 3;
            // 目标元素的下标位置，默认-1
            int index = -1;
            // 低位
            int low = 0;
            // 高位
            int high = arr.length - 1;
    
            // 查找最后一个值等于给定值的元素
            while (low <= high) {
                // 中位
                int mid = (low + high) / 2;
                // 如果中间元素大于目标元素，说明查找的元素在数组左边范围，缩小查找范围，高位变为 high = mid - 1，继续查找
                if (arr[mid] > target) {
                    high = mid - 1;
                } else if (arr[mid] < target) {
                    // 如果中间元素小于目标元素，说明查找的元素在数组右边范围，缩小查找范围，地位变为 low = mid + 1，继续查找
                    low = mid + 1;
                } else if (arr[mid] == target){// 查找到目标元素，需要继续往前查找最后一个等于目标元素的元素
                    // 最后一位元素等于目标元素 或 目标元素的后一个元素已经不是目标值，则当前位元素就是最后一个等于目标元素的值
                    if (mid == arr.length - 1 || arr[mid + 1] != target) {
                        index = mid;
                        break;
                    } else {
                        // 继续进行二分查找最后一个等于目标值的元素，继续查找
                        low = mid + 1;
                    }
                }
            }
    
            // 结果输出
            if (index >= 0) {
                System.out.println("target-index = " + index + ", target-value = " + arr[index]);
            } else {
                System.out.println("Target element not found");
            }
        }
    }

# 二分查找变种3：查找第一个值大于等于给定值的元素。 #

package com.jpeony.algorithm.binarysearch;
    
    /**
     * 【变体3】：查找第一个值大于等于给定值的元素
     *
     * @author yihonglei
     */
    public class SearchFirstGreaterThanTarget {
        public static void main(String[] args) {
            // 查找数组
            int[] arr = {1, 2, 4, 5, 6, 7, 8, 9};
            // 目标值
            int target = 3;
            // 目标值元素下标，默认-1
            int index = -1;
            // 低位
            int low = 0;
            // 高位
            int high = arr.length - 1;
    
            // 查找第一个值大于等于给定值的元素
            while (low <= high) {
                // 中位
                int mid = (low + high) / 2;
                // 如果中间元素大于等于目标元素，说明查找的元素在数组左边范围
                if (arr[mid] >= target) {
                    // 第一位元素等于目标元素 或 目标元素的前一个元素小于目标元素，则当前位元素就是第一个大于等于目标元素的值
                    if (mid == 0 || arr[mid - 1] < target) {
                        index = mid;
                        break;
                    } else {
                        // 缩小查找范围，高位变为 high = mid - 1，继续查找
                        high = mid - 1;
                    }
                } else if (arr[mid] < target) {
                    // 缩小查找范围，低位变为 low = mid + 1，继续查找
                    low = mid + 1;
                }
            }
    
            // 结果输出
            if (index >= 0) {
                System.out.println("target-index = " + index + ", target-value = " + arr[index]);
            } else {
                System.out.println("Target element not found");
            }
        }
    }

# 二分查找变种4：查找最后一个值小于等于给定值的元素。 #

package com.jpeony.algorithm.binarysearch;
    
    /**
     * 【变体4】：查找最后一个值小于等于给定值的元素
     *
     * @author yihonglei
     */
    public class SearchLastLessThanTarget {
        public static void main(String[] args) {
            // 查找数组
            int[] arr = {1, 2, 4, 5, 6, 7, 8, 9};
            // 目标元素
            int target = 3;
            // 目标元素的下标位置，默认-1
            int index = -1;
            // 低位
            int low = 0;
            // 高位
            int high = arr.length - 1;
    
            // 查找最后一个值小于等于给定值的元素
            while (low <= high) {
                // 中位
                int mid = (low + high) / 2;
                // 如果中间元素大于等于目标元素，说明查找的元素在数组左边范围
                if (arr[mid] > target) {
                    high = mid - 1;
                } else if (arr[mid] <= target) {
                    // 最后一位元素等于目标元素 或 目标元素的后一个元素大于目标元素，则当前位元素就是最后一个大于等于目标元素的值
                    if (mid == arr.length - 1 || arr[mid + 1] > target) {
                        index = mid;
                        break;
                    } else {
                        // 缩小查找范围，低位变为 low = mid + 1，继续查找
                        low = mid - 1;
                    }
                }
            }
    
            // 结果输出
            if (index >= 0) {
                System.out.println("target-index = " + index + ", target-value = " + arr[index]);
            } else {
                System.out.println("Target element not found");
            }
        }
    }

[https_github.com_yihonglei_road-of-arch]: https://github.com/yihonglei/road-of-arch