精华内容
参与话题
问答
  • 插值查找是二分查找的更高效版本,它不会每次按2平分原问题规模,而是应用一个技巧来尽快的接近目标关键字。 示例 public class Program { public static void Main(string[] args) { int[] array = { 8, 11, 21,...

    插值查找是二分查找的更高效版本,它不会每次按2平分原问题规模,而是应用一个技巧来尽快的接近目标关键字。

    示例

    public class Program {
    
        public static void Main(string[] args) {
            int[] array = { 8, 11, 21, 28, 32, 43, 48, 56, 69, 72, 80, 94 };
    
            Console.WriteLine(InterpolationSearch(array, 80, 0, array.Length - 1));
    
            Console.ReadKey();
        }
    
        private static int InterpolationSearch(int[] array, int key, int low, int high) {
            if (low > high) return -1;
            var mid = (int)(low + ((double)key - array[low]) / 
                (array[high] - array[low]) * (high - low));
            if (array[mid] == key)
                return mid;
            else if (array[mid] > key)
                return InterpolationSearch(array, key, low, mid - 1);
            else
                return InterpolationSearch(array, key, mid + 1, high);
        }
    
    }
    

    在最坏的情况下插值查找的时间复杂度为: O(log(logn)) 。

    展开全文
  • Python实现插值查找算法,插值查找和二分查找

    阅读目录

    思路

    • 概述
      在这里插入图片描述
      变换一下,插值查找求的mid_index为:
      mid_index = left+(right-left) * ( val-array[left] ) / ( array[right]-array[left] )

    • 举例说明
      在这里插入图片描述

    Python实现

    # 要求数组是有序的
    def insert_value_search(array, left, right, val):
        if left > right or val < array[0] or array[right-1] < val: # 注意后半部分的判断条件
            return -1
        mid_index = left + (right - left) * (val - array[left]) // (array[right] - array[left])
        mid_val = array[mid_index]
        if mid_val < val:
            return insert_value_search(array, mid_index + 1, right, val)
        elif val < mid_val:
            return insert_value_search(array, left, mid_index - 1, val)
        else:
            return mid_index
    
    
    if __name__ == '__main__':
        li=[]
        for i in range(100):
            li.append(i+1)
        print(insert_value_search(li, 0, len(li) - 1, 3))
    

    插值查找和二分查找比较

    def binary_search(array, left, right, val):
        print("二分查找被调用")
        if left > right:
            return []
        mid_index = (left + right) >> 1
        if val < array[mid_index]:
            return binary_search(array, left, mid_index - 1, val)
        elif array[mid_index] < val:
            return binary_search(array, mid_index + 1, right, val)
        else:
            res_list = []
            temp = mid_index - 1
            while True:
                if temp < 0 or array[temp] != array[mid_index]:
                    break
                res_list.append(temp)
                temp -= 1
            temp = mid_index + 1
            res_list.append(mid_index)
            while True:
                if temp > len(array) - 1 or array[temp] != array[mid_index]:
                    break
                res_list.append(temp)
                temp += 1
            return res_list
    
    
    def insert_value_search(array, left, right, val):
        print("插值查找被调用")
        if left > right or val < array[0] or array[right - 1] < val:
            return -1
        mid_index = left + (right - left) * (val - array[left]) // (array[right] - array[left])
        mid_val = array[mid_index]
        if mid_val < val:
            return insert_value_search(array, mid_index + 1, right, val)
        elif val < mid_val:
            return insert_value_search(array, left, mid_index - 1, val)
        else:
            return mid_index
    
    
    if __name__ == '__main__':
        li = []
        for i in range(100):
            li.append(i + 1)
        print(insert_value_search(li, 0, len(li) - 1, 55))
        print(binary_search(li, 0, len(li) - 1, 55))
    '''
    插值查找被调用
    54
    二分查找被调用
    二分查找被调用
    二分查找被调用
    二分查找被调用
    二分查找被调用
    二分查找被调用
    二分查找被调用
    [54]
    '''
    
    • 总结:
      - 看以看到在有序序列查找,插值查找要优于二分法查找
    展开全文
  • 二分查找,插值查找,斐波那契查找: 1.二分查找: 伪代码: while(left begin if key == arr[left] or key == arr[right] or key == arr[left+right/2] return index else if key[(left+index)/2] then right = ...

    二分查找,插值查找,斐波那契查找:

    1.二分查找:
    伪代码:

    while(left<right)
    begin
    if key == arr[left] or key == arr[right] or key == arr[left+right/2]
    return index

    else if key< arr[(left+index)/2]
    then right = (left+right)/2
    else
    left = (left+right)/2
    end

    示例代码:

    public int MidSearch(List<int> arr, int searchValue)
            {
                if (arr == null || arr.Count == 0)
                    return -1;
                if (arr.Count == 1)
                    return arr[0] == searchValue ? 0 : -1;
                var lowIndex = 0;
                var highIndex = arr.Count - 1;
    
                while (lowIndex < highIndex)
                {
                    if (arr[lowIndex] == searchValue) return lowIndex;
                    if (arr[highIndex] == searchValue) return highIndex;
                    var midIndex = (lowIndex + highIndex) / 2;
                    if (arr[midIndex] == searchValue) return midIndex;
                    if (arr[midIndex] < searchValue)
                    {
                        lowIndex = midIndex + 1;
                    }
                    else
                    {
                        highIndex = midIndex - 1;
                    }
                }
                return -1;
            }


    2.插值查找:
    Note:区别在于二分法在计算中值索引时候一直是/2 ,而插值查找的关键在于查找公式。

    思路与二分法一样,只是计算索引时把mid = (left+right)/2 替换为:
    left + (key - arr[left]) * (right - left) / (arr[right] - arr[left]);

    示例代码:

     

    public int InterpolationSearch(List<int> arr, int searchValue)
            {
                if (arr == null || arr.Count == 0)
                    return -1;
                if (arr.Count == 1)
                    return arr[0] == searchValue ? 0 : -1;
                var lowIndex = 0;
                var highIndex = arr.Count - 1;
    
                while (lowIndex < highIndex)
                {
                    if (arr[lowIndex] == searchValue) return lowIndex;
                    if (arr[highIndex] == searchValue) return highIndex;
                    var midIndex = lowIndex + (searchValue - arr[lowIndex]) * (highIndex - lowIndex) / (arr[highIndex] - arr[lowIndex]);
                    if (arr[midIndex] == searchValue) return midIndex;
                    if (arr[midIndex] < searchValue)
                    {
                        lowIndex = midIndex + 1;
                    }
                    else
                    {
                        highIndex = midIndex - 1;
                    }
                }
                return -1;
            }

    3.斐波那契查找:
    1.建立斐波那契数组
    2.查找

    示例代码:
      

    private void F_InitOnce()
            {
                if (F == null)
                {
                    F = new List<int>();
                    //init Fibonacci array
                    F.Add(1);
                    F.Add(1);
                    for (int i = 2; i < 50; i++)
                    {
                        F.Add(F[i - 1] + F[i - 2]);
                    }
                }
            }
            public int FibonacciSearch(List<int> arr, int key)
            {
                int low, high, mid, k, n;
                low = 0;
                n = arr.Count;
                high = arr.Count;
                k = 0;
                while (n > F[k] - 1) k++;
                while (low <= high)
                {
                    mid = low + F[k - 1] - 1;
                    if (key < arr[mid])
                    {
                        high = mid - 1;
                        --k;
                    }
                    else if (key > arr[mid])
                    {
                        low = mid + 1;
                        k = k - 2;
                    }
                    else
                    {
                        return n;
                    }
                }
    
                return -1;
            }

     

    UT:

     

          [TestMethod]
            public void MidSearch()
            {
                var arr = new List<int>() { 1, 4, 8, 29, 31, 45, 78, 90, 102, 167, 220 };
                var searcher = new SearchStudy();
                for (var i = 0; i < arr.Count; i++)
                {
                    var ret = searcher.InterpolationSearch(arr, arr[i]);
                    Assert.AreEqual(ret, i);
                }
                var toBeSearched = 32;
                var ret2 = searcher.MidSearch(arr, toBeSearched);
                Assert.AreEqual(ret2, -1);
            }
            [TestMethod]
            public void InterpolationSearch()
            {
                var arr = new List<int>() { 1, 4, 8, 29, 31, 45, 78, 90, 102, 167, 220 };
                var searcher = new SearchStudy();
                for (var i = 0; i < arr.Count; i++)
                {
                    var ret = searcher.InterpolationSearch(arr, arr[i]);
                    Assert.AreEqual(ret, i);
                }
                var cannotFind = 32;
                var ret2 = searcher.InterpolationSearch(arr, cannotFind);
                Assert.AreEqual(ret2, -1);
            }
            [TestMethod]
            public void FibonacciSearch()
            {
                var arr = new List<int>() { 1, 4, 8, 29, 31, 45, 78, 90, 102, 167, 220 };
                var searcher = new SearchStudy();
                for (var i = 0; i < arr.Count; i++)
                {
                    var ret = searcher.FibonacciSearch(arr, arr[i]);
                    Assert.AreEqual(ret, i);
                }
                var cannotFind = 32;
                var ret2 = searcher.FibonacciSearch(arr, cannotFind);
                Assert.AreEqual(ret2, -1);
            }


     

    展开全文
  • 插值查找

    千次阅读 2020-04-29 18:10:31
    插值查找,有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。 1)插值查找原理介绍: 插值查找...

    插值查找,有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。

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

    2)将折半查找中的求    mid索引的公式   , low表示左边索引   left, high表示右边索引  right.
    key就是前面我们讲的     findVal
     

    插值查找的前提是有序数列元素的值是成线性增长的(这个假设的精确度会影响算法的效率,但不会影响算法的正确性)。对于大多数有序数列来说,这前提是可以成立的。我们不妨假设它就是成立的,那样,当我们知道一个要查找值的大小后。就可以根据数列线性增长的性质,求出要查找的值在数列中的大概位置

    比如说在数列A[lo,hi)中查找e。我们设e的下标为mi。由于数列线性增长,我们不难得到这个等式:


            进而得出:

     

    package com.atguigu;
    
    public class InsertValueSearch {
    
    	public static void main(String[] args) {
    
    
    		int arr[] = { 1, 8, 10, 89,1000, 1234 };
    
    		int index = insertValueSearch(arr, 0, arr.length - 1, 1000);
    
    		System.out.println("index = " + index);
    
    	}
    	//编写插值查找算法
    	//说明:插值查找算法,也要求数组是有序的
    	/**
    	 *
    	 * @param arr 数组
    	 * @param left 左边索引
    	 * @param right 右边索引
    	 * @param findVal 查找值
    	 * @return 如果找到,就返回对应的下标,如果没有找到,返回-1
    	 */
    	public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
    
    		System.out.println("插值查找次数~~");
    
    		//注意:findVal < arr[0]  和  findVal > arr[arr.length - 1] 必须需要
    		//否则我们得到的 mid 可能越界
    		if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
    			return -1;
    		}
    
    		// 求出mid, 自适应
    		int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
    		int midVal = arr[mid];
    		if (findVal > midVal) { // 说明应该向右边递归
    			return insertValueSearch(arr, mid + 1, right, findVal);
    		} else if (findVal < midVal) { // 说明向左递归查找
    			return insertValueSearch(arr, left, mid - 1, findVal);
    		} else {
    			return mid;
    		}
    
    	}
    }
    

     

    时间复杂度

    插值查找的时间复杂度也是O(logN)O(logN)。

    注意事项

    1. 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找, 速度较快.
    2. 关键字分布不均匀的情况下,该方法不一定比折半查找要好
    展开全文
  • 插值查找和折半查找的思想是一样的,其代码机构也基本和折半查询相同: //折半查找 public int Binary_Search(int[] a, int n, int key) { int low = 1, high = n, mid; while(low &lt;= high) { mid = ...
  • 二分查找,O(logn)的经典查找算法,实现在一个非下降序列中快速查找一个值是否...插值查找是对二分查找的一个扩展,对于接近线性递增的序列效率极高,其他情况效率一般。 斐波那契查找,纯娱乐用的东西,存在意义不明?
  • Scala练习-插值查找

    2017-07-05 23:08:35
    原理 源码 package day15 import day14.Utils import day15.BinarySearch.printlnArrayimport scala.collection.mutable.ArrayBuffer/** ... * 插值查找:改进二分查找的算法,在数值范围比较大,分布比较均匀时可以

空空如也

1 2 3 4 5 ... 20
收藏数 1,828
精华内容 731
关键字:

插值查找