java数据结构和算法——二分查找算法(非递归方式实现)

一、二分查找算法的介绍

• 二分查找又称为折半查找
• 假设表中元素是按升序排列（必须是有序列表），将表中间位置记录的关键字与查找关键字比较
• 如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字则进一步查找前一子表；否则进一步查找后一子表。
• 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

二、二分查找算法的示例需求

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

三、二分查找算法的代码实现示例（非递归方式）

1、代码

package com.rf.springboot01.Algorithm.binarySearchNorecursion;

/**
 * @description:  二分查找算法类（非递归实现）
 * @author: xiaozhi
 * @create: 2020-10-29 21:53
 */
public class BinarySearchNoRecur {
    public static void main(String[] args) {
        int[] arr = {1,3, 8, 10, 11, 67, 100};
        int index1 = binarySearch(arr, 1);
        System.out.println("指定数组元素1的下标为========" + index1);
        int index8 = binarySearch(arr, 8);
        System.out.println("指定数组元素8的下标为========" + index8);
        int index67 = binarySearch(arr, 67);
        System.out.println("指定数组元素67的下标为========" + index67);
        int index99 = binarySearch(arr, 99);
        System.out.println("指定数组元素99的下标为========" + index99);
    }

    /** 
    * @Description: 二分查找的非递归实现
    * @Param:  arr 待查找的数组, arr是升序排序
    * @Param: target 需要查找的数
    * @Author: xz  
    * @return: 返回对应下标，-1表示没有找到
    * @Date: 2020/10/29 21:56
    */
    public static int binarySearch(int[] arr,int target){
        int left =0;//左侧下标
        int right=arr.length-1;//右侧下标
        while(left  target){
                right = mid - 1;//需要向左边查找
            }else{
                left = mid + 1; //需要向右边查找
            }
        }
        return -1;
    }
}

2、运行main函数，测试结果如下：