查找算法--------二分查找算法

末蓝、 2022-04-23 01:28 409阅读 0赞

# 二分查找算法 #

## 1.二分查找又称折半查找 ##

优点：比较次数少，查找速度快，平均性能好

缺点：待查表为有序表

## 2.注意事项 ##

(left+right)/2:会出现溢出的现象
    判断条件是中间位置的值是否小于0
    我们的对比条件就已经排除mid下标的值，所以可以放心的-/+ 1,而且这样会符合二的条件避免死循环！

## 3.代码逻辑步骤 ##

① 首先确定整个查找区间的中间位置 mid = left + (right - left) / 2;
    ② 用待查关键字值与中间位置的关键字值进行比较；
    　 若相等，则查找成功
    　 若大于，则在后（右）半个区域继续进行折半查找
    　 若小于，则在前（左）半个区域继续进行折半查找
    ③ 对确定的缩小区域再按折半公式，重复上述步骤。

## 4.算法使用条件 ##

1.存储在顺序表中

2.有序排列

## 5.实现方法分为递归方法和非递归方法 ##

### 5.1 非递归方法 ###

private static int notRecursion(int[] intArr, int num) { 
            int left = 0;
            int right = intArr.length;
            //结束条件
            while (left <= right) { 
                //不要写成mid = （ left + right ）/ 2 相加可能会发生越界
                int mid = left + (right - left) / 2;
                if (intArr[mid] == num) { 
                    return mid;
                } else if (intArr[mid] > num) { 
                    //避免死循环
                    right = mid-1;
                } else if (intArr[mid] < num) { 
                    //避免死循环
                    left = mid+1;
                }
            }
            return -1;
        }

### 5.2递归方法 ###

private static int Recursion(int[] intArr, int left, int right, int num) { 
            int mid = left + (right - left) / 2;
            if (intArr[mid] == num) { 
                return mid;
            }else if (left >= right) { 
                return -1;
            } else if (num > intArr[mid]) { 
                return Recursion(intArr, mid + 1, right, num);
            } else if (num < intArr[mid]) { 
                return Recursion(intArr, left, mid - 1, num);
            }
            return -1;
        }

### 5.3 主方法 ###

public static void main(String[] args) { 
            int[] intArr = new int[]{ 1, 2, 3, 4, 5};
            int notrecursion = notRecursion(intArr, 5);
            int recursion = Recursion(intArr, 0, intArr.length-1, 1);
            System.out.println(notrecursion);
            System.out.println(recursion);
        }

***版权声明：本博客为记录本人自学感悟，转载需注明出处！***  
[https://me.csdn.net/qq\_39657909][https_me.csdn.net_qq_39657909]

[https_me.csdn.net_qq_39657909]: https://me.csdn.net/qq_39657909