二分查找（Binary Search）是一种高效的查找算法，也叫折半查找。核心思想：对于一个有序的数据集合，每次查找都将查找范围缩小为原来的一半，直到找到目标值或确定目标值不存在。二分查找要求数据必须是有序的，经常应用于数组等支持随机访问的数据结构里。跟线性查找相比，二分查找的效率要高得多，特别是对于大规模数据集。
核心特性：
下面是二分查找算法在各种主流编程语言中的实现：
public class BinarySearch {
// 迭代实现
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left target) {
right = mid - 1;
}
// 在右半部分继续查找
else {
left = mid + 1;
}
}
// 未找到目标值
return -1;
}
// 递归实现
public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
return binarySearchRecursive(arr, target, left, mid - 1);
} else {
return binarySearchRecursive(arr, target, mid + 1, right);
}
}
// 测试
public static void main(String[] args) {
int[] arr = {2, 3, 4, 10, 40, 50, 70, 80};
int target = 10;
// 迭代方法
int result = binarySearch(arr, target);
if (result == -1) {
System.out.println("元素 " + target + " 不存在于数组中");
} else {
System.out.println("元素 " + target + " 在数组中的索引为 " + result);
}
// 递归方法
result = binarySearchRecursive(arr, target, 0, arr.length - 1);
if (result == -1) {
System.out.println("元素 " + target + " 不存在于数组中");
} else {
System.out.println("元素 " + target + " 在数组中的索引为 " + result);
}
}
}
二分查找在很多场景中都有广泛的应用：
哈希查找（Hash Search），又称散列查找，是一种高效的查找算法，它用哈希函数将数据转换为数组下标，然后直接访问数组中的元素。哈希查找的核心思想是将数据元素通过哈希函数映射到哈希表中的位置，实现快速查找。
在理想情况下，哈希查找的时间复杂度为 O(1)，这就意味着无论数据规模多大，查找操作都能在常数时间内完成，这是哈希查找相比其他查找算法（如二分查找、线性查找）的最大优势。
不过使用哈希查找必须要考虑哈希冲突（不同的数据被映射到相同的位置）问题。
核心特性：
public class HashSearch {
// 哈希表节点类
static class Node {
String key;
int value;
Node next;
public Node(String key, int value) {
this.key = key;
this.value = value;
this.next = null;
}
}
// 哈希表类
static class HashTable {
private Node[] buckets;
private int capacity;
private int size;
private final float LOAD_FACTOR = 0.75f; // 负载因子阈值
public HashTable(int capacity) {
this.capacity = capacity;
this.buckets = new Node[capacity];
this.size = 0;
}
// 哈希函数
private int hash(String key) {
int hash = 0;
for (char c : key.toCharArray()) {
hash = (hash * 31 + c) % capacity;
}
return Math.abs(hash);
}
// 插入键值对
public void put(String key, int value) {
if ((float)size / capacity >= LOAD_FACTOR) {
resize(2 * capacity);
}
int index = hash(key);
Node newNode = new Node(key, value);
// 如果桶为空，直接插入
if (buckets[index] == null) {
buckets[index] = newNode;
size++;
return;
}
// 处理哈希冲突，使用链地址法
Node current = buckets[index];
// 检查是否已存在相同的键
while (current != null) {
if (current.key.equals(key)) {
current.value = value; // 更新值
return;
}
if (current.next == null) {
break;
}
current = current.next;
}
// 在链表末尾添加新节点
current.next = newNode;
size++;
}
// 查找键对应的值
public Integer get(String key) {
int index = hash(key);
Node current = buckets[index];
// 遍历链表查找匹配的键
while (current != null) {
if (current.key.equals(key)) {
return current.value;
}
current = current.next;
}
// 未找到
return null;
}
// 删除键值对
public boolean remove(String key) {
int index = hash(key);
Node current = buckets[index];
Node prev = null;
// 查找目标节点
while (current != null) {
if (current.key.equals(key)) {
break;
}
prev = current;
current = current.next;
}
// 未找到目标节点
if (current == null) {
return false;
}
// 删除节点
if (prev == null) {
buckets[index] = current.next;
} else {
prev.next = current.next;
}
size--;
return true;
}
// 扩容并重新哈希
private void resize(int newCapacity) {
Node[] oldBuckets = buckets;
// 创建新的哈希表
buckets = new Node[newCapacity];
capacity = newCapacity;
size = 0;
// 重新哈希所有元素
for (Node bucket : oldBuckets) {
Node current = bucket;
while (current != null) {
put(current.key, current.value);
current = current.next;
}
}
}
}
public static void main(String[] args) {
HashTable hashTable = new HashTable(10);
// 插入数据
hashTable.put("apple", 5);
hashTable.put("banana", 10);
hashTable.put("orange", 15);
hashTable.put("grape", 20);
// 查找数据
System.out.println("apple: " + hashTable.get("apple"));
System.out.println("banana: " + hashTable.get("banana"));
System.out.println("orange: " + hashTable.get("orange"));
System.out.println("grape: " + hashTable.get("grape"));
System.out.println("watermelon: " + hashTable.get("watermelon"));
// 删除数据
hashTable.remove("orange");
System.out.println("After removing orange: " + hashTable.get("orange"));
}
}
哈希查找适用于以下场景：
一致性哈希是分布式系统中的重要概念，目的是尽可能少地重新分配数据
详情可以看一致性哈希算法
布隆过滤器是一种空间效率高的概率型数据结构，判断一个元素是否在集合中
详情可以看布隆过滤器
本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top
登录查看全部
参与评论
手机查看
返回顶部