java 算法二分查找和折半查找
java 算法二分查找与折半查找
折半查找 :首先数组是已经排好序的
实例代码:
package com.hao.myrxjava; /** * 折半查找 :首先数组是已经排好序的 * * @author zhanghaohao * @date 2017/5/15 */ public class HalfDivision { /** * 循环实现 * * @param array 排好序的数组 * @param value 查找的值 * @return value在array的位置 */ public static int halfDivision(int value, int[] array) { if (array == null || array.length == 0) throw new NullPointerException("array is null"); int low = 0; int high = array.length - 1; int mid = (low+high)/2; while (array[mid] != value) { if (array[mid] > value) high = mid - 1; else low = mid + 1; if (low > high) return -1; mid = (low+high)/2; if (array[mid] == value) return mid; } return mid; } /** * 递归实现 * * @param array 排好序的数组 * @param value 查找的值 * @param low 查找的起始位置 * @param high 查找的末尾位置 * @return value在array的位置 */ public static int halfDivision(int value, int[] array, int low, int high) { if (low > high) return -1; int mid = (low + high) / 2; if (array[mid] == value) return mid; else if (array[mid] > value) return halfDivision(value, array, low, mid - 1); else if (array[mid] < value) return halfDivision(value, array, mid+1, high); return -1; } }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关推荐
-
Java实现二分查找算法实例分析
本文实例讲述了Java实现二分查找算法.分享给大家供大家参考.具体如下: 1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合
-
Java使用二分法进行查找和排序的示例
实现二分法查找 二分法查找,需要数组内是一个有序的序列 二分查找比线性查找:数组的元素数越多,效率提高的越明显 二分查找的效率表示:O(log2N) N在2的M次幂范围,那查找的次数最大就是M, log2N表示2的M次幂等于N, 省略常数,简写成O(logN) 如有一个200个元素的有序数组,那么二分查找的最大次数: 2^7=128, 2^8=256, 可以看出7次幂达不到200,8次幂包括, 所以最大查找次数就等于8 //循环,二分查找 static int binarySearch(int
-
java算法之二分查找法的实例详解
java算法之二分查找法的实例详解 原理 假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则返回其索引,否则返回-1.通过数组长度可取出中间位置元素的索引,将其值与目标值比较,如果中间位置元素值大于目标值,则在左部分进行查找,如果中间位置值小于目标值,则在右部分进行查找,如此循环,直到结束.二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能找到目标或确定其不存在,当然前提是查找范围为有序数组. Java的简单实现 package me
-
Java经典算法汇总之顺序查找(Sequential Search)
a)原理:顺序查找就是按顺序从头到尾依次往下查找,找到数据,则提前结束查找,找不到便一直查找下去,直到数据最后一位. b)图例说明: 原始数据:int[]a={4,6,2,8,1,9,0,3}; 要查找数字:8 找到数组中存在数据8,返回位置. 代码演示: import java.util.Scanner; /* * 顺序查找 */ public class SequelSearch { public static void main(String[] arg) { int[] a={4,6,2
-
Java实现的快速查找算法示例
本文实例讲述了Java实现的快速查找算法.分享给大家供大家参考,具体如下: 快速查找算法,可以根据想要找的是第几个大的数,每次循环都能固定下来一个数在数组完整排完序之后的位置,每次循环都能定一个数的位置,如果当前固定的数的位置和用户要找的第几个数匹配,则就直接返回.例如我要找第二大的数,如果循环一次固定的数的下标是1,那就是当前需要找的数. 代码如下: // 快速查找算法 public static int quickSelect(int[] arr, int selectIndex) { in
-
java二分查找插入法
复制代码 代码如下: package uv; public class Bean implements Comparable<Bean> {String sessionId;Integer num = 1;public String getSessionId() {return sessionId;}public void setSessionId(String sessionId) {this.sessionId = sessionId;}public Integer getNum()
-
Java实现的两种常见简单查找算法示例【快速查找与二分查找】
本文实例讲述了Java实现的两种常见简单查找算法.分享给大家供大家参考,具体如下: 前言: 查找是指从一批记录当中找出满足制定条件的某一记录的过程. 在平常的程序的编写当中很多时候时用得上的,这里简单介绍两个查找算法 1. 快速查找: 这个是相当简单的,以数组举例,就用一个for循环去查找数组中需要查找的数据 例子: public static boolean quickSearch(int a[], int x) { boolean f = false; int length = a.leng
-
Java正则表达式实现在文本中匹配查找换行符的方法【经典实例】
本文实例讲述了Java正则表达式实现在文本中匹配查找换行符的方法.分享给大家供大家参考,具体如下: 默认情况下,正则表达式 ^ 和 $ 忽略行结束符,仅分别与整个输入序列的开头和结尾匹配.如果激活 MULTILINE 模式,则 ^ 在输入的开头和行结束符之后(输入的结尾)才发生匹配.处于 MULTILINE 模式中时,$ 仅在行结束符之前或输入序列的结尾处匹配. NLMatch.java: package nlMatch; import java.util.regex.Pattern; /**
-
java 折半查找法(二分查找)实例
复制代码 代码如下: public class HalfSearch { public static int halfSearch(int a[], int x) { int mid, left, right; left = 0; right = a.length - 1; mid = (left + right) / 2; while (a[mid] != x) { if (x > a[mid]) { left = mid + 1; } else if (x <
-
java 算法二分查找和折半查找
java 算法二分查找与折半查找 折半查找 :首先数组是已经排好序的 实例代码: package com.hao.myrxjava; /** * 折半查找 :首先数组是已经排好序的 * * @author zhanghaohao * @date 2017/5/15 */ public class HalfDivision { /** * 循环实现 * * @param array 排好序的数组 * @param value 查找的值 * @return value在array的位置 */ pu
-
PHP有序表查找之二分查找(折半查找)算法示例
本文实例讲述了PHP有序表查找之二分查找(折半查找)算法.分享给大家供大家参考,具体如下: 简介: 二分查找技术,又称为折半查找.它的前提是线性表中的记录必须是关键码有序(通常从小到达有序),线性表必须采用顺序存储. 基本思想: 在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功:若给定值小于中间记录的关键字,则在中间记录的左半区继续查找:若给定值大于中间记录的关键字,则在中间记录的右半区继续查找.不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止.
-
剑指Offer之Java算法习题精讲数组查找与字符串交集
题目一 数组题--二分查找法 写一个函数查找给定的数组中指定的数值 具体题目如下 解法 class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while(left<=right){ int mid = left+(right-left)/2; if(nums[mid]==target){ return mid; }else if(nums[m
-
Java 选择、冒泡排序、折半查找(实例讲解)
如下所示: //选择排序对数据进行升序排序 public static void selectSortArray(int[] arr){ for(int i = 0; i<arr.length-1;i++){ for(int j = i+1;j<arr.length;j++){ if(arr[i]>arr[j]){ int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } } } //冒泡排序对数据进行升序排序 public stati
-
C语言实现顺序表的顺序查找和折半查找
本文实例为大家分享了C语言实现顺序表的顺序查找和折半查找的具体代码,供大家参考,具体内容如下 顺序查找: #include <iostream> using namespace std; int SeqSearch(int r[],int n,int k) { r[0]=k;//下标0用作哨兵存放要查询的数 int i=n; while(r[i]!=k)//不用判断下标i是否越界 { i--; } return i; } int main() { int n; cout<<&quo
-
Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)
目录 1.查找概述 2.顺序查找 3.二分查找 3.1 二分查找概述 3.2 二分查找实现 4.插值查找 4.1 插值查找概述 4.2 插值查找实现 5.斐波那契查找 5.1 斐波那契查找概述 5.2 斐波那契查找实现 5.3 总结 1.查找概述 查找表: 所有需要被查的数据所在的集合,我们给它一个统称叫查找表.查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合. 查找(Searching): 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录).
-
C++二分查找(折半查找)算法实例详解
本文实例讲述了C++二分查找(折半查找)算法.分享给大家供大家参考,具体如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难. 因此,折半查找方法适用于不经常变动而查找频繁的有序列表. 二分查找思想 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功: 否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 重复
-
PHP有序表查找之插值查找算法示例
本文实例讲述了PHP有序表查找之插值查找算法.分享给大家供大家参考,具体如下: 前言: 在前面我们介绍了二分查找,但是我们考虑一下,为什么一定要折半呢?而不是折四分之一或者更多? 打个比方,在英文词典里查找"apple",你下意识里翻开词典是翻前面的书页还是后面的书页呢?如果再查"zoo",你又会怎么查?显然你不会从词典中间开始查起,而是有一定目的地往前或往后翻. 同样,比如要在取值范围在 0 ~ 10000 之间的100个元素从小到大均匀分布的数组中查找5,我们自
随机推荐
- 提高代码性能技巧谈—以创建千行表格为例
- java实现动态代理方法浅析
- iOS 懒加载的使用实例代码
- 在IOS中为什么使用多线程及多线程实现的三种方法
- php过滤html标记属性类用法实例
- 用JS控制回车事件的代码
- python集合类型用法分析
- ubuntu使用root用户登录/切换root权限的实现
- MSSQL数据加密解密代码
- jQuery插件扩展操作入门示例
- js实现的星星评分功能函数
- C++中构造函数重载
- 浅析Android手机卫士读取联系人
- Spring boot实现文件上传实例(多文件上传)
- tomcat301与java301解析
- java,Android:在eclipse中的快捷键(经典收藏)
- PHP 自动加载的简单实现(推荐)
- C语言中设置用户识别码的相关函数的简单讲解
- java实现中缀表达式转后缀的方法
- YII2.0框架行为(Behavior)深入详解