十种常用算法之二分查找（java版）

十大常用算法的完整实现

一、二分查找算法：https://blog.csdn.net/weixin_46635575/article/details/121532149
二、分治算法：https://blog.csdn.net/weixin_46635575/article/details/121532941
三、动态规划算法：https://blog.csdn.net/weixin_46635575/article/details/121534074
四、KMP算法：https://blog.csdn.net/weixin_46635575/article/details/121590510
五、贪心算法：https://blog.csdn.net/weixin_46635575/article/details/121626626
六、普利姆算法：https://blog.csdn.net/weixin_46635575/article/details/121653256
七、克鲁斯卡尔算法：https://blog.csdn.net/weixin_46635575/article/details/121670374
八、地杰斯特拉算法：https://blog.csdn.net/weixin_46635575/article/details/121692675
九、佛洛依德算法：https://blog.csdn.net/weixin_46635575/article/details/121714678
十、马踏棋盘算法（周游骑士算法）：https://blog.csdn.net/weixin_46635575/article/details/121716596

1、递归版的实现

https://blog.csdn.net/weixin_46635575/article/details/121055514

2、非递归的基本介绍

2、非递归代码会实现

比较简单

package cn.mldn;


public class binarySearch {
    public static void main(String[] args) {
        int [] arr = {1,3,4,6,8,10,14};
        System.out.println(binarySearch(arr,3));
        System.out.println(binarySearch(arr,9));
    }


    /**
     * 二分查找的非递归实现
     * @param arr 待查找的数组，且是升序的
     * @param target 待查找的值
     * @return
     */
    public static int binarySearch(int[] arr,int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {//只要满足这个条件就可以继续查找
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                //这时候不能递归
                right = mid - 1;//需要向左边查找
            } else {
                left = mid + 1;//需要向右边查找
            }
        }
        //只要循环结束，说明找到了，在此之前就返回了
        return -1;//说明没有找到
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

运行结果