本文主要介绍了Java编程开发入门到精通-数据结构与算法「二分查找非递归」，通过具体的内容向大家展现，希望对大家Java开发的学习有所帮助。

基本介绍

1.二分查找只适用于从有序的数列中进行查找(比如数字和字母)，将数列排序后再进行查找。

2.二分查找法的运行时间为对数时间O(log2n),即查找到需要的目标位置最多只需log2n步，假设从[0,99]的队列中寻找目标数30，则需要查找步数为log2(100)，即最多需要7次(2^6<100<2^7)。

代码案例

package com.xie.algorithm;

public class BinarySearchNoRecur {

    public static void main(String[] args) {

        int[] arr = {1, 3, 8, 10, 11, 67, 100};

        int index = binarySearch(arr, 1);

        System.out.println("index = " + index);

    }

    /**

     * 二分查找非递归实现

     *

     * @param arr    待查找的数组,arr是升序排列

     * @param target 需要查找的数

     * @return 返回对应的下标 ，-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 = mid + 1;

            }

        }

        return -1;

    }

}

基本介绍

1.插值查找算法类似于二分查找，不同的是插值查找每次从自适应的mid处开始查找。

2.二分查找中求mid索引的公式转成插值查找mid索引公式，low表示左边的索引，high表示右边的索引，key表示要查找的值

代码案例

package com.xie.search;

import java.util.ArrayList;

import java.util.List;

public class InsertValueSearch {

    static int count = 0;

    public static void main(String[] args) {

        int[] arr = new int[102];

        arr[0] = 1;

        arr[1] = 1;

        for (int i = 2; i < 102; i++) {

            arr[i] = i;

        }

        List<Integer> indexList = insertValueSearch(arr, 0, arr.length - 1, 1);

        System.out.println("indexList = " + indexList);

        System.out.println("查找次数：" + count);

        /*

        indexList = [1, 0]

        查找次数：1

         */

    }

    /**

     * 插值查找，返回索引集合

     *

     * @param arr       数组

     * @param left      左边索引

     * @param right     右边索引

     * @param findValue 要查找的值

     * @return 找到就返回所有索引的集合，没有就返回空

     */

    public static List<Integer> insertValueSearch(int[] arr, int left, int right, int findValue) {

        count++;

        List<Integer> indexList = new ArrayList<Integer>();

        //注意：findValue < arr[0] || findValue > arr[arr.length - 1] 这个必须要，否则mid可能越界

        if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) {

            return new ArrayList<Integer>();

        }

        int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);

        int midValue = arr[mid];

        if (findValue > midValue) {

            return insertValueSearch(arr, mid + 1, right, findValue);

        } else if (findValue < midValue) {

            return insertValueSearch(arr, left, mid - 1, findValue);

        } else {

            //如果找到了，再向左扫描，将满足条件的加入indexList

            int temp = mid - 1;

            while (true) {

                if (temp < 0 || arr[temp] != findValue) {

                    break;

                }

                indexList.add(temp);

                temp--;

            }

            //再向右扫描,将满足条件的加入indexList

            temp = mid + 1;

            while (true) {

                if (temp > right || arr[temp] != findValue) {

                    break;

                }

                indexList.add(temp);

                temp++;

            }

            indexList.add(mid);

            return indexList;

        }

    }

} 

我是小职，记得找我

✅ 解锁高薪工作

✅ 免费获取基础课程·答疑解惑·职业测评