精华内容
下载资源
问答
  • java基础-数组的折半查找原理  作者:尹正杰 版权声明:原创作品,谢绝转载!否则将追究法律责任。      如果让你写一个数组的查找功能,需求如下:在一个数组中,找一个元素,是否存在于数组中, 如果存在就...

                      java基础-数组的折半查找原理

                                        作者:尹正杰

    版权声明:原创作品,谢绝转载!否则将追究法律责任。

     

     

      如果让你写一个数组的查找功能,需求如下:在一个数组中,找一个元素,是否存在于数组中, 如果存在就返回这个元素,如果没有这个元素,就可以返回一个负数。今天我们来介绍一下折半查找的原理,并自己用代码实现折半查找。

     

     

    一.数组的折半查找原理

      二分查找发,也叫折半查找,它的前提就是被查找的数组的元素,必须是有序(本篇博客数据案例均为升序)排列的。

    1>.在查找前对数组进行折半操作 (初始化指针位置)  

      折半公式 =  (最大索引+最小索引)/ 2

       首先我们可以利用指针思想,假设有一个指针指向最大值(MAX),有一个指针指向最小值(MIN),还有一个指针指向的是最大值和最小值之间的索引(MID)。我把这个过程称为初始化指针位置。

    2>.折半后的指针索引和被查找元素比较。

      若被查找元素的值(12)大于中间索引上的值(10),我们就把最小值指针(MIN)移动到中间指针(MID)索引的下一个索引位置,如下图:

    3>.若没有匹配到就继续折半后的指针索引和被查找元素比较。 

     

       若被查找元素的值(12)小于中间索引上的值(15),我们就把最大值指针(MAX)移动到中间指针(MID)索引的上一个索引位置,如下图:

     

    4>.若没有匹配到就继续折半后的指针索引和被查找元素比较。 

      若被查找元素的值(12)小于中间索引上的值(13),我们就把最大值指针(MAX)移动到中间指针(MID)索引的上一个索引位置,如下图:

     

    5>.若没有匹配到就继续折半后的指针索引和被查找元素比较。 

      当小指针(MIN)的索引(4)超过了大指针(MAX)的索引(3)时,就需要停止查找了,如果真有这种情况发生,说明没有查到被查找元素的值(12),此时会返回一个负数(-1),当然如果查找到了就返回其在数组中的索引即可。

    二.数组的折半查找代码实现

     1 /*
     2 @author :yinzhengjie
     3 Blog:http://www.cnblogs.com/yinzhengjie/tag/Java%E5%9F%BA%E7%A1%80/
     4 EMAIL:y1053419035@qq.com
     5 */
     6 
     7 package cn.org.yinzhengjie.demo;
     8 
     9 public class Demo {
    10 
    11     public static void main(String[] args) {
    12         int[] arr = {1,4,7,10,13,15,21,25};
    13         int index = binarySearch(arr,12);
    14         System.out.println(index);
    15         index = binarySearch(arr,7);
    16         System.out.println(index);
    17     }
    18 
    19     public static int binarySearch(int[] arr,int key) {
    20         //定义三个指针变量。
    21         int min = 0;
    22         int max = arr.length - 1;
    23         int mid = 0;
    24         //循环折半,条件, min<=max
    25         while(min <= max) {
    26             //公式,计算中间索引
    27             mid = (min+max)/2;
    28             //让被找元素和中间索引元素进行比较
    29             if(key>arr[mid]) {
    30                 min = mid +1;
    31             }else if(key <arr[mid]) {
    32                 max = mid -1;
    33             }else {
    34                 //找到元素,返回元素索引
    35                 return mid;
    36             }
    37         }
    38         return -1;
    39     }
    40 }
    41 
    42 
    43 /*
    44 以上代码执行结果如下:
    45 -1
    46 2
    47 */
     1 /*
     2 @author :yinzhengjie
     3 Blog:http://www.cnblogs.com/yinzhengjie/tag/Java%E5%9F%BA%E7%A1%80/
     4 EMAIL:y1053419035@qq.com
     5 */
     6 
     7 package cn.org.yinzhengjie.note;
     8 
     9 /*
    10  * 二分查找
    11  * 折半查找
    12  *     前提:要找的数组必须是有序的.
    13  *     每次都用中间的元素和要找的元素进行比较
    14  * 
    15  */
    16 public class BinarySearchDemo {
    17 
    18     public static void main(String[] args) {
    19         int[] arr = {1,4,7,10,13,15,21,25};
    20         int index = binarySearch(arr,21);
    21         //对返回值进行判断
    22         if(index == -1){
    23             System.out.println("no such element");
    24         }else{
    25             System.out.println("index is : " + index);
    26         }
    27     }
    28     
    29     
    30     //自定义方法,折半查找
    31     public static int binarySearch(int[] arr,int value){
    32         int min = 0;
    33         int max = arr.length - 1;
    34         int mid = (min + max) / 2;
    35         while(true){    
    36             //判断要找的数落在左边还是右边
    37             if(value > arr[mid]){
    38                 min = mid + 1;
    39             }else if(value < arr[mid]){
    40                 max = mid - 1;
    41             }else{
    42                 return mid;
    43             }
    44             //重新计算中间的索引值
    45             mid = (min + max) / 2;
    46             //没有找到的条件判断
    47             if(min > max){
    48                 return -1;
    49             }
    50         }
    51     }
    52 }
    53 
    54 
    55 /*
    56 以上代码执行结果如下:
    57 index is : 6
    58 */
    另一种二分法查找的实现方式

     

    展开全文
  • 前提:被查找的数组中...折半后的索引上的元素和被查找的元素比较,  查找的元素 > 索引上的元素,则minIndex = 中间索引+1;  查找的元素 < 索引上的元素,则maxIndex = 中间索引-1;  如果 minIndex ...

    前提:被查找的数组中的元素必须要是有序的排列

      公式 (maxIndex + minIndex)/2 获得中间索引;

      ps:若出现小数,则取个位数。

     折半后的索引上的元素和被查找的元素比较,

      查找的元素 > 索引上的元素,则minIndex = 中间索引+1;

      查找的元素 < 索引上的元素,则maxIndex = 中间索引-1;

      如果 minIndex > maxIndex 程序结束,没找到。

      如果查找的元素==索引上的元素,则该元素就在其中间索引。

      

    转载于:https://www.cnblogs.com/ccbk/p/9404597.html

    展开全文
  • 折半查找原理(C++)

    2018-06-07 19:08:32
    #include&lt;stdio.h&gt; #include&lt;iostream&gt; using namespace std; int find(int a[],int num) { int low=0; int high=8; int mid=(low+high)/2; while(a[mid]!... return -...
    #include<stdio.h>
    #include<iostream>
    using namespace std;
    
    int find(int a[],int num)
    {
    	int low=0;
    	int high=8;
    	int mid=(low+high)/2;
    	while(a[mid]!=num)
    	{
    		if(high<=low)
    			return -1;
    		cout<<"high="<<high<<endl;
    		cout<<"low="<<low<<endl;
    		cout<<"mid="<<mid<<endl;
    		if(num>a[mid]) low=mid+1;
    		else high=mid-1;
    		mid=(high+low)/2;
    
    	}
    	/*while(high>=low)
    	{
    		cout<<"high="<<high<<endl;
    		cout<<"low="<<low<<endl;
    		cout<<"mid="<<mid<<endl;
    		if(a[mid]==num)return mid;
    		else if(a[mid]>num)high=mid-1;
    		else low=mid+1;
    		mid=(high+low)/2;
    	}*/
    	return mid;
    }
    void main()
    {
    	int nums[10]={1,2,3,4,5,6,7,8,9};
    	int pos;
    	int num;
    	cin>>num;
    	pos=find(nums,num);
    	cout<<pos<<endl;
    }

    展开全文
  • 主要介绍了JavaScript折半查找(二分查找)算法原理与实现方法,结合具体问题描述了折半查找算法的原理、实现方法及相关操作注意事项,需要的朋友可以参考下
  • 折半查找原理及其java的两种实现

    千次阅读 2017-03-07 21:58:19
    折半查找原理及其java的两种实现

            二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

    public static int binSearch(int nums[], int des) {
    		int low = 0;
    		int high = nums.length - 1;
    		int middle = 0;
    		while (low <= high) {
    			middle = low + (high - low) / 2;//避免溢出
    			if (nums[middle] == des)
    				return middle;
    			else if (nums[middle] > des)
    				high = middle - 1;
    			else
    				low = middle + 1;
    		}
    		return -1;
    	}
    
    	public static int Search(int nums[], int des, int begin, int end) {
    		int middle = begin + (end - begin) / 2 ;//避免溢出
    		if (nums[middle] == des);
    		else if (nums[middle] > des)
    			middle = Search(nums, des, begin, middle - 1);
    		else
    			middle = Search(nums, des, middle + 1, end);
    		return middle;
    	}


    展开全文
  • 折半查找

    2017-03-26 00:03:34
    折半查找的具体程序
  • 折半查找(二分查找)原理的基本实现 import java.util.Arrays; import java.util.Random; import java.util.Scanner; public class BinarySearch { public static void main(String[] args) { @...
  • 顺序查找和折半查找

    2020-11-28 13:23:42
    折半查找1)折半查找原理:2)折半查找举例:3)举例:使用折半方法查找数组中某元素的索引,并统计出查找次数3.顺序查找和折半查找 1.顺序查找 顺序查找就是从数组的第一个元素开始,依次比较,直到找到目标数据或...
  • 文章目录查找查找的概念顺序查找顺序查找-算法原理顺序查找-算法实现顺序查找-性能分析折半查找折半查找-算法原理折半查找-算法实现折半查找-性能分析分块查找分块查找-算法原理分块查找-算法实现分块查找-性能分析 ...
  • package practice;...public class 二分查找 { public static int[] maopao(int[] args) {//可以接收也可以不接收 for (int i = 0; i < args.length; i++) { for (int j = 0; j < args.length -...
  • 主要介绍了PHP实现的折半查找算法,简单描述了折半查找原理,并结合实例形式分析了php采用递归与非递归方式实现折半查找算法的相关操作技巧,需要的朋友可以参考下
  • 【查找算法】折半查找

    千次阅读 2020-02-20 17:08:09
    本篇文章将介绍折半...这个时候,折半查找诞生了,它的原理是每次都将待查找的记录所在的区间缩小一半,比如: 若要在该序列中查找元素值4,折半查找是如何做到的呢? 它需要先设置两个游标,一个指向最左边,一...
  • 主要介绍了基于JavaScript实现的折半查找算法,结合实例形式分析了折半查找原理、操作步骤及javascript实现折半查找的相关操作技巧与注意事项,需要的朋友可以参考下
  • 折半查找 原理:是一种二分查找方法。首先确定待查元素的范围,然后不断缩小区间,直到查找成功或者失败。 注意:折半查找判定树。 时间复杂度: #include<iostream> #include<algorithm> #include...
  • 查找_折半查找(C语言)

    2020-07-18 15:38:24
    1.查找原理 折半查找(Binary Search)也称二分查找,是一种效率较高的查找方法,但是折半查找有局限性,它只适用于顺序存储结构的有序表 查找过程:从表的中间位置开始,判断与给定的值是否相等,若相等则查找...
  • 主要介绍了PHP有序表查找之二分查找(折半查找)算法,简单介绍了二分查找法的概念、原理并结合实例形式分析了php基于二分查找算法进行有序线性表查找的相关操作技巧,需要的朋友可以参考下
  • 概要引入折半查找基本概念折半查找java代码实现折半查找算法复杂度分析折半查找改进版1:插值查找折半查找改进版2:斐波那契查找总结 引入 顺序查找虽然算法非常简单,对静态查找表的记录没有任何要求,但是当查找...
  • 主要介绍了C++二分查找(折半查找)算法,结合实例形式详细分析了二分查找算法的原理、思想、实现方法与相关操作技巧,需要的朋友可以参考下
  • 折半查找

    2019-11-08 17:12:54
    折半查找 问题 输入:一个升序数组A[0…n-1]和一个查找键K,用折半查找算法实现如下功能, 输出:一个数组元素的下标,该元素等于K;如果没有这样一个元素,则返回-1。 实验原理 在键盘上输入数组长度,查找的元素,...
  • 插值查找是在折半查找的基础上进行了改进,所以这个方法是在有序表的基础上进行查找,主要应用于分布比较均匀的有序表,而对不均匀的表不适用。 其算法主要基于折半查找,对 mid 进行优化与调整。判断 key 值与 a...
  • 递归的折半查找算法

    千次阅读 2019-02-19 10:02:08
    问题一:递归的折半查找算法 注意:折半查找有一个条件,数据必须是有顺序性的,不然折半查找毫无意义; 原问题:有一数组A[10],里面存放了十个整数,顺序递增。任意输入一个n(位于数组里外均可),如果n数与数组...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,818
精华内容 3,927
关键字:

折半查找原理