关于java:我所知道的查找算法之二分查找非递归

前言需要

后面咱们有一起分享学习过：二分查找算法

遗记了的同学小伙伴能够再点击看看，那么咱们之前的形式是采纳递归的形式

明天咱们须要学习的是采纳：非递归的形式 实现二分查找算法

一、二分查找算法介绍

首先能够让咱们回顾一下二分查找算法的一些特点，比如说：

是一种 在有序数组中查找某一特定元素 的搜索算法。

1. 搜寻过程 从数组的两头元素开始 ，如果 两头元素正好 是要 查找的元素 ，则 搜寻完结

2. 如果 某一特定元素大于或者小于两头元素 ，则 在数组大于或小于两头元素的那一半中 查找，而且 从新开始从两头元素 进行比拟。

3. 如果 在某一步骤数组为空 ，则代表 找不到 。这种搜索算法 每一次比拟都使搜寻范畴放大一半

咱们晓得的工夫复杂度为 O(logn)，即假如从 [0-99] 的队列中查找指标数 30，则须要查问的步数最多为： 7 次（2^6 < n <2 ^ 7）

二、通过示例学习非递归形式实现

数组{1, 3, 8, 10, 11, 67, 100}, 编程实现二分查找，要求应用非递归的形式实现.

/**
 * @param arr 待查找的数组
 * @param target 须要查找的数
 * @retum 返回找到的下标，没有则返回 -1
 */
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 = left + 1;}
    }
    return -1;
}

接下来咱们查问数据：11 看看

public static void main(String[] args) {int[] arr = {1, 3, 8, 10, 11, 67, 100};
    int index = binarySearch(arr,11);
    System.out.println("index =>" + index);
}

运行后果如下：index =>4

接下来咱们查问数据：22 看看

public static void main(String[] args) {int[] arr = {1, 3, 8, 10, 11, 67, 100};
    int index = binarySearch(arr,22);
    System.out.println("index =>" + index);
}

运行后果如下：index => -1