前言

提示：以下是本篇文章正文内容，仅供参考

一、二分查找思路

二分查找只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找 二分查找法的运行时间为对数时间O(log2 n)，即查找到需要的目标位置最多只需要log2 n步，假设从0~99的数列中(n=100)中寻找目标数30，则只需要查找步数log2 100，最多查找7次 二分查找的思路（递归）：

1、首先确定该数组的中间的下标 mid = (left + right) / 2 2、然后让需要查找的数findVal和arr[mid]比较 2.1 findVal > arr[mid] ，说明你要查找的数在mid的右边，因此需要递归的向右查找 2.2 findVal < arr[mid] ，说明你要查找的数在mid的左边，因此需要递归的向左查找 2.3 findVal = arr[mid] ，说明找到，就返回 什么时候结束递归？ 找到就结束递归 递归完整个数组，仍然没有找到findVal，也需要结束递归，即当left > right 就需要退出递归

二、代码实现

1.递归实现

代码如下（示例）：

package com.yang;

/**
 * 二分查找非递归
 *
 * 二分查找只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找
 * 二分查找法的运行时间为对数时间O(log2 n)，即查找到需要的目标位置最多只需要log2 n步，假设从0~99的数列中(n=100)中寻找目标数30，则只需要查找步数log2 100，最多查找7次
 *
 * 二分查找的思路：
 * 1、首先确定该数组的中间的下标
 * mid = (left + right) / 2
 * 2、然后让需要查找的数findVal和arr[mid]比较
 *  2.1 findVal > arr[mid] ，说明你要查找的数在mid的右边，因此需要递归的向右查找
 *  2.2 findVal < arr[mid] ，说明你要查找的数在mid的左边，因此需要递归的向左查找
 *  2.3 findVal = arr[mid] ，说明找到，就返回
 *
 *  什么时候结束递归？
 *  1) 找到就结束递归
 *  2) 递归完整个数组，仍然没有找到findVal，也需要结束递归，即当left > right 就需要退出递归
 *
 * @Author: tututuyang
 * @Date: 2021/6/28 12:41
 * @Description:
 */
public class BinarySearch {
          
   

    public static void main(String[] args) {
          
   
        int[] arr = {
          
   1,4,6,9,10,15,20};
        int findVal = 9;
        System.out.println(binarySearch(arr, 0, arr.length, findVal));
        System.out.println(binarySearchNoRecur(arr, findVal));
    }

    /**
     * @param arr 数组
     * @param left 左边的索引
     * @param right 右边的索引
     * @param findVal 目标数
     * @return 如果找到就返回下标，没找到就返回-1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
          
   

        if (left > right) {
          
   
            return -1;
        }
        int mid = (left + right) / 2;

        if (arr[mid] == findVal) {
          
   
            return mid;
        } else if (arr[mid] > findVal) {
          
   
            // 向左边查找
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
          
   
            // 向右边查找
            return binarySearch(arr, mid + 1, right, findVal);
        }
    }

    
}

2.非递归实现

代码如下（示例）：

/**
     *
     * @param arr
     * @param findVal
     * @return
     */
    public static int binarySearchNoRecur(int[] arr, int findVal) {
          
   

        int left = 0;
        int right = arr.length - left;
        while (left <= right) {
          
   
            int mid = (left + right) / 2;
            if (arr[mid] == findVal) {
          
   
                return mid;
            } else if (arr[mid] > findVal) {
          
   
                // 向左边查找
                right = mid - 1;
            } else {
          
   
                // 向右边查找
                left = mid + 1;
            }
        }
        return -1;
    }

总结

以上就是今天要记录的内容