二分查找算法（Java实现）

不念不忘少年蓝@ 2022-05-20 10:17 195阅读 0赞

### **①适用于经常查找的、但是不变的（增删）的有序列表。** ###

## ##

### **②原理图** ###

### **![70][]** ###

### **③测试代码：** ###

//二分查找测试类
    //注意：二分查找必须用在有序列表中进行二分查找
    public class BinaryChopTest {
           public static void main(String[] args) {
            int[] arrays = {1, 6, 10, 11, 12, 100};
            for (int i = 0; i <= 10; i++) {
                int sign = recursionBinarySearch(arrays, i, 0, arrays.length - 1);
                if (sign == -1) {
                    System.out.println("在数组中找不到" + i + "这个元素");
                    System.out.println("目标元素" + i + "在数组的第" + sign + "位置");
                }
                sign = -1;
            }
        }
    
        /**
         *      * 使用二分查找和递归的结合进行查找
         *      * 时间复杂度：O(logN)
         *      * @param arrays    有序数组
         *      * @param target    要查找的元素(目标元素)
         *      * @param low        最低位
         *      * @param high        最高位
         *      * @return         找到的位置
         *     
         */
        public static int recursionBinarySearch(int[] arrays, int target, int low, int high){
            if (target < arrays[low] || target > arrays[high] || low > high) {
                return -1;
            }
            int middle = (low + high) / 2; //初始化中间位置的值
            if (arrays[middle] > target) {
                return recursionBinarySearch(arrays, target, low, middle - 1);
            } else if (arrays[middle] < target) {
                return recursionBinarySearch(arrays, target, middle + 1, high);
            } else {
                return middle;
            }
        }
    }

###      ###

### **④测试结果** ###

### **![70 1][]** ###

[70]: /images/20220520/a57839cd9f4c4d13ac3b61074c33d5f7.png
[70 1]: /images/20220520/1f2511aeebfc4e8b88decda1c27b04af.png