Java编程内功-数据结构与算法「二分查找非递归」

时间:2021-08-16 23:11:09

Java编程内功-数据结构与算法「二分查找非递归」

基本介绍

 

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

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

代码案例

 

  1. package com.xie.algorithm; 
  2.  
  3. public class BinarySearchNoRecur { 
  4.     public static void main(String[] args) { 
  5.         int[] arr = {1, 3, 8, 10, 11, 67, 100}; 
  6.         int index = binarySearch(arr, 1); 
  7.         System.out.println("index = " + index); 
  8.     } 
  9.  
  10.     /** 
  11.      * 二分查找非递归实现 
  12.      * 
  13.      * @param arr    待查找的数组,arr是升序排列 
  14.      * @param target 需要查找的数 
  15.      * @return 返回对应的下标 ,-1 表示没有找到 
  16.      */ 
  17.     public static int binarySearch(int[] arr, int target) { 
  18.         int left = 0; 
  19.         int right = arr.length - 1; 
  20.         while (left <= right) { 
  21.             int mid = (left + right) / 2; 
  22.             if (arr[mid] == target) { 
  23.                 return mid; 
  24.             } else if (arr[mid] > target) { 
  25.                 //需要向左边查找 
  26.                 right = mid - 1; 
  27.  
  28.             } else { 
  29.                 //需要向右边查找; 
  30.                 left = mid + 1; 
  31.             } 
  32.         } 
  33.         return -1; 
  34.     } 

基本介绍

 

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

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

Java编程内功-数据结构与算法「二分查找非递归」

代码案例

 

  1. package com.xie.search; 
  2.  
  3. import java.util.ArrayList; 
  4. import java.util.List; 
  5.  
  6. public class InsertValueSearch { 
  7.     static int count = 0; 
  8.  
  9.     public static void main(String[] args) { 
  10.         int[] arr = new int[102]; 
  11.         arr[0] = 1; 
  12.         arr[1] = 1; 
  13.         for (int i = 2; i < 102; i++) { 
  14.             arr[i] = i; 
  15.         } 
  16.         List<Integer> indexList = insertValueSearch(arr, 0, arr.length - 1, 1); 
  17.         System.out.println("indexList = " + indexList); 
  18.         System.out.println("查找次数:" + count); 
  19.  
  20.         /* 
  21.         indexList = [1, 0] 
  22.         查找次数:1 
  23.          */ 
  24.     } 
  25.  
  26.     /** 
  27.      * 插值查找,返回索引集合 
  28.      * 
  29.      * @param arr       数组 
  30.      * @param left      左边索引 
  31.      * @param right     右边索引 
  32.      * @param findValue 要查找的值 
  33.      * @return 找到就返回所有索引的集合,没有就返回空 
  34.      */ 
  35.     public static List<Integer> insertValueSearch(int[] arr, int leftint rightint findValue) { 
  36.         count++; 
  37.         List<Integer> indexList = new ArrayList<Integer>(); 
  38.         //注意:findValue < arr[0] || findValue > arr[arr.length - 1] 这个必须要,否则mid可能越界 
  39.         if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) { 
  40.             return new ArrayList<Integer>(); 
  41.         } 
  42.         int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]); 
  43.         int midValue = arr[mid]; 
  44.  
  45.         if (findValue > midValue) { 
  46.             return insertValueSearch(arr, mid + 1, right, findValue); 
  47.         } else if (findValue < midValue) { 
  48.             return insertValueSearch(arr, left, mid - 1, findValue); 
  49.         } else { 
  50.             //如果找到了,再向左扫描,将满足条件的加入indexList 
  51.             int temp = mid - 1; 
  52.             while (true) { 
  53.                 if (temp < 0 || arr[temp] != findValue) { 
  54.                     break; 
  55.                 } 
  56.                 indexList.add(temp); 
  57.                 temp--; 
  58.             } 
  59.  
  60.             //再向右扫描,将满足条件的加入indexList 
  61.             temp = mid + 1; 
  62.             while (true) { 
  63.                 if (temp > right || arr[temp] != findValue) { 
  64.                     break; 
  65.                 } 
  66.                 indexList.add(temp); 
  67.                 temp++; 
  68.             } 
  69.             indexList.add(mid); 
  70.             return indexList; 
  71.         } 
  72.     } 

注意事项

 

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

原文地址:https://www.toutiao.com/i6939142586317799968/