关于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