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;         }     } } 

注意事项

对于数据量大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快。 关键字分布不均匀的情况下，该方法不一定比二分法要好。