java排序--折半查找

曾经终败给现在 2022-09-20 05:47 168阅读 0赞

**1.概念:**

**折半查找，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的**[**搜索算法**][Link 1]**。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。**

**2.代码一:**

**/\*\***

** \* **

** \* @param x 被查找的数组(有序)**

** \* @param key 查找特定的元素**

** \* @return 找到元素返回元素在数组中的位置,没有找到就返回\-1**

** \*/**

**public static <T extends Comparable<T>> int binarySearchsort(T\[\] x, T key) \{**

** **

**int low = 0;//起点元素**

**int hight = x.length - 1;//终点元素**

** **

**while (low <= hight) \{**

**//中间元素**

**int mid = low + ((hight - low) >> 1);**

**//如果要查找的元素等于中间元素**

**if (key.compareTo(x\[mid\]) == 0) \{**

**return mid;**

**//如果要查找的元素大于中间元素 ,low=mid+1**

**\} else if (key.compareTo(x\[mid\]) > 0) \{**

**low = mid + 1;**

**//如果要查找的元素小于中间元素 ,hight = mid-1**

**\} else if (key.compareTo(x\[mid\]) < 0) \{**

**hight = mid -1;**

**\}**

**\}**

**return -1;**

**\}**

**3.代码二:**

**递归实现**

**private static<T extends Comparable<T>> int binarySearch(T\[\] x, int low, int high, T key) \{**

**if(low <= high) \{**

**int mid = low + ((high - low) >> 1);**

**if(key.compareTo(x\[mid\]) == 0) \{**

**return mid;**

**\}**

**else if(key.compareTo(x\[mid\]) < 0) \{**

**return binarySearch(x, low, mid - 1, key);**

**\}**

**else \{**

**return binarySearch(x, mid + 1, high, key);**

**\}**

**\}**

**return -1;**

**\}**

**\}**

注意:计算中间位置时，不应该使用(high + low) / 2的方式，因为加法运算可能导致整数越界，这里应该使用一下三种方式之一：low + (high – low) / 2或low + (high – low) >> 1或（low + high） >>> 1（注：>>>是逻辑右移，不带符号位的右移）

[Link 1]: http://zh.wikipedia.org/w/index.php?title=%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95&action=edit&redlink=1

发表评论取消回复

表情：

评论列表（有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读

相关二分查找、折半查找（Java）

目录 7.3 二分（折半）查找二分查找（递归）二分查找（非递归） 7

骑猪看日落/ 2024年04月07日 10:27/ 0 赞/ 84 阅读

相关折半查找

include<stdio.h> include<stdlib> int BinarySearch(int arr[],int size,in

朱雀/ 2023年06月13日 11:25/ 0 赞/ 173 阅读

相关 java排序--折半查找

1.概念: 折半查找，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的[搜索算法][Link 1]。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元

曾经终败给现在/ 2022年09月20日 05:47/ 0 赞/ 169 阅读

相关二分查找(折半查找) -- 已排序序列的查找算法

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。 -

怼烎@/ 2022年07月24日 06:21/ 0 赞/ 211 阅读

相关折半查找

![Center][] ![Center 1][] [Center]: https://img-blog.csdn.net/20170411111131574?waterm

短命女/ 2022年06月17日 00:12/ 0 赞/ 224 阅读

相关折半查找

递归算法： int binarysearch(int a,int key,int low,int high) { if(low>hi

冷不防/ 2022年06月08日 14:58/ 0 赞/ 254 阅读

相关折半查找

1、折半查找又称二分查找，它仅适用于有序表。 2、基本思路：在有序表中取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间的记录的关键字，则

朴灿烈づ我的快乐病毒、/ 2022年06月06日 00:49/ 0 赞/ 276 阅读

相关折半查找、快速排序

折半查找循环实现 ''' 折半查找循环实现 ''' def binarySearch(list, key):

川长思鸟来/ 2022年06月04日 03:37/ 0 赞/ 161 阅读

相关 Java选择排序与折半查找

package 选择排序与折半查找; import java.util.;//表示这个包下所有的类库 public class Ex

以你之姓@/ 2022年05月25日 06:41/ 0 赞/ 142 阅读

相关折半查找

package test; public class Search \{ > /\\ > \ 折半查找 > > \ @param a数组,key 要查找的数

刺骨的言语ヽ痛彻心扉/ 2022年05月17日 01:06/ 0 赞/ 224 阅读