查找算法-二分查找的几种变体
程序员文章站
2022-03-14 23:16:52
...
唐纳德·克努特(Donald E.Knuth)在《计算机程序设计艺术》第三卷中说:“尽管第一个二分查找算法出现于1946年,然而第一个完全正确的二分查找算法直到1962年才出现。”
简单的二分查找算法是比较容易《查找算法-有序数组的二分查找》,但是并不常用,因为简单的二分查找算法没有考虑重复数据的情况,而现实情况则是常有重复数据,于是本节列举的是二分查找的几种常见变体。
查找第一个值等于给定值的元素
/**
* 查找第一个值等于给定值的元素
* @param a
* @param n
* @param value
* @return
*/
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == 0) || (a[mid - 1] != value)) return mid;
else high = mid - 1;
}
}
return -1;
}
查找最后一个值等于给定值的元素
/**
* 查找最后一个值等于给定值的元素
* @param a
* @param n
* @param value
* @return
*/
public int bsearch2(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
else low = mid + 1;
}
}
return -1;
}
查找第一个大于等于给定值的元素
/**
* 查找第一个大于等于给定值的元素
* @param a
* @param n
* @param value
* @return
*/
public int bsearch3(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) return mid;
else high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
查找最后一个小于等于给定值的元素
/**
* 查找最后一个小于等于给定值的元素
* @param a
* @param n
* @param value
* @return
*/
public int bsearch4(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else {
if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
else low = mid + 1;
}
}
return -1;
}
在循环有序数组中使用二分查找给定值
package com.study.algorithm.search;
/**
* 在循环有序数组中使用二分查找给定值,时间复杂度O(logN)
* 比如:4,5,6,1,2,3
* ps:[4,5,6,1,2,3]是有序数组[1,2,3,4,5,6]的变体
*/
public class BinaryCycleSort {
private int[] nums;
private int target;
public int find_rotate_index(int left, int right) {
//数组本身有序,非循环有序
if (nums[left] < nums[right]){
return 0;
}
while (left <= right) {
int pivot = (left + right) / 2;
if (nums[pivot] > nums[pivot + 1]){
return pivot + 1;
}else {
if (nums[pivot] < nums[left]){
right = pivot - 1;
} else{
left = pivot + 1;
}
}
}
return 0;
}
/**
* Binary search
* @param left
* @param right
* @return
*/
public int search(int left, int right) {
while (left <= right) {
int pivot = (left + right) / 2;
if (nums[pivot] == target){
return pivot;
} else {
if (target < nums[pivot]){
right = pivot - 1;
}else{
left = pivot + 1;
}
}
}
return -1;
}
public int search(int[] nums, int target) {
this.nums = nums;
this.target = target;
int n = nums.length;
if (n == 0){
return -1;
}
if (n == 1) {
return this.nums[0] == target ? 0 : -1;
}
//查找循环有序数组的分界点
int rotate_index = find_rotate_index(0, n - 1);
// 此时的target是整个数组的最小元素
if (nums[rotate_index] == target){
return rotate_index;
}
// 如果数组不是循环有序,即使整个有序,则在着整个数组中查找目标值
if (rotate_index == 0){
return search(0, n - 1);
}
//如果目标值小于数组第一个元素,则在分界点右边数组查找
if (target < nums[0]){
// search in the right side
return search(rotate_index, n - 1);
}
//如果目标值大于数组第一个元素,则在分界点左边数组查找
return search(0, rotate_index);
}
}
上一篇: Java常用加密工具 ( MD5,sha1,SHA256)
下一篇: MD5以及SHA1加密