09 |二分查找

一、二分查找的思想

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
二分查找的效率非常之高，时间复杂度为O(log(N)),这是一个相当惊人的时间复杂度。

二、二分查找的递归和非递归实现

一.递归实现

递归调用方法实现

二.非递归实现

while循环实现

三.递归和非递归的代码实现

package binarysearch;

public class binarySearchDemo {
   
     
    public static void main(String[] args) {
   
     
        //已经排好序的数组
        int[] MergeArray = {
   
     8, 11, 19, 23, 27, 33, 45, 55, 67, 98};//
        //需要寻找得值
        int tagret1 = 67;
        int tagret2 = 8;
        //排序方法
        binarySearchByRecursion(MergeArray, tagret2, 0, MergeArray.length - 1);

        binarySearchByWhile(MergeArray, tagret1, 0, MergeArray.length - 1);
    }

    //递归算法
    public static void binarySearchByRecursion(int[] MergeArray, int tagret, int indexlow, int indexhigt) {
   
     

        //1如果目标数据小于当前范围最小数据。2目标数据大于当前范围最大数据
        if (tagret > MergeArray[indexhigt] || tagret < MergeArray[indexlow]) {
   
     
            return;
        }
        int indexMiddle = indexlow + (indexhigt - indexlow) / 2;

        if (MergeArray[indexMiddle] > tagret) {
   
     
            binarySearchByRecursion(MergeArray, tagret, indexlow, indexMiddle - 1);
        } else if (MergeArray[indexMiddle] < tagret) {
   
     
            binarySearchByRecursion(MergeArray, tagret, indexMiddle + 1, indexhigt);
        } else if (MergeArray[indexMiddle] == tagret) {
   
     
            System.out.printf("找到目标数据" + MergeArray[indexMiddle]);
        } else {
   
     
            System.out.println("目标数据不在数据范围内");
        }
    }

    //WHILE查找
    public static void binarySearchByWhile(int[] MergeArray, int tagret, int indexlow, int indexhigt) {
   
     

        if (indexlow > indexhigt) {
   
     
            return;
        }
        while (indexlow <= indexhigt) {
   
     

            int indexMiddle = indexlow + (indexhigt - indexlow) / 2;
            if (indexhigt == indexlow && indexhigt - indexlow == 0) {
   
     
                if (MergeArray[indexMiddle] == MergeArray[indexlow]) {
   
     
                    System.out.printf("找到目标数据" + MergeArray[indexMiddle]);
                    return;
                }
            } else if (MergeArray[indexMiddle] > tagret) {
   
     
                indexhigt = indexMiddle - 1;
            } else if (MergeArray[indexMiddle] < tagret) {
   
     
                indexlow = indexMiddle + 1;

            } else if (MergeArray[indexMiddle] == tagret) {
   
     
                System.out.printf("找到目标数据" + MergeArray[indexMiddle]);
                return;
            } else {
   
     
                System.out.println("目标数据不在数据范围内");
                return;
            }
        }
    }
}