二分查找法(Binary Search)以及其变种floor和c
2019-07-26 本文已影响0人
叫我胖虎大人
对于有序数列才能使用二分查找法(排序的作用)
基本思想:将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
一般的二分查找法
public class BinarySearch {
/**
* @param arr 传入的数组
* @param n 数组的大小
* @param target 需要查找的值
* @return 返回的位置,如果没有找到就返回-1
*/
static int binarySearch(int[] arr,int n,int target){
//在arr[l..r]之中查找target
int l = 0,r = n-1;
while (l < r){
//(l+r)/2会产生程序溢出的问题(其中一个值接近int的最大值的时候)
int mid = l + (r-l)/2;
if (arr[mid] == target){
return mid;
}
if (target < arr[mid]){
//在arr[l...mid-1]之中查找target
r = mid - 1;
}else {
//在arr[mid+1..r]之中查找target
l = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,7,8,9};
System.out.println(binarySearch(arr,arr.length,3));
}
}
递归的二分查找法
对递归实现通常上思维更加简单,但是性能上会略差
/**
* 二分查找的递归实现方式
* @param arr 数组
* @param left 数组的左边界
* @param right 数组的右边界
* @param target 目标值
* @return
*/
static int binarySearch2(int[] arr,int left,int right,int target){
//在边界范围以内
if (left < right){
int mid = left+(right-left)/2;
if(arr[mid] == target){
return mid;
}
if (arr[mid] < target){
return binarySearch2(arr,mid+1,right,target);
}else {
return binarySearch2(arr,left,mid-1,target);
}
}
return -1;
}
二分查找的变种形式
对于上述两种二分查找方式,当数组中存在重复元素的时候就会显得有些鸡肋,这里就引入了二分查找法的变种形式
- 当存在大量重复的元素时，floor找的是第一个，ceil找的是第一个。
- 当不存在指定的元素时，floor是比其小最大的一个，而ceil是比其大最小的一个。
public class BinarySearch2
{
/**
* 用于寻找目标值第一次出现的位置
* @param arr 数组
* @param target 目标值
* @return 目标值第一次出现的位置,如果没有找到就是最接近目标值(左边)的位置
*/
private static int floor(Comparable[] arr, Comparable target){
//寻找比target小的最大索引(left设置为-1是因为有可能最左边的元素也有可能不是目标值)
//与下面的right设置为arr.length是一样的性质
int left = -1;
int right = arr.length-1;
while (left < right){
int mid = left + (right - left+1)/2;
//中间值大于目标值 选择左边区域
if (arr[mid].compareTo(target) >= 0){
right = mid - 1;
}else {
left = mid;
}
}
// 如果该索引+1就是target本身, 该索引+1即为返回值
if( left + 1 < arr.length && arr[left+1] == target ) {
return left + 1;
}
// 否则, 该索引即为返回值
return left;
}
/**
* 用于寻找目标值最后一次出现的位置
* @param arr 数组
* @param target 目标值
* @return 目标值第一次出现的位置,如果没有找到就是最接近目标值(右边)的位置
*/
private static int ceil(Comparable[] arr,Comparable target){
//寻找比target大的最小索引
int left = 0;
int right = arr.length;
while (left < right){
//注意与上面去中间值的区别
int mid = left + (right - left)/2;
//中间值小于目标值
if( arr[mid].compareTo(target) <= 0 ){
left = mid + 1;
}else {
right = mid - 1;
}
}
//如果索引-1就是目标值本上,该索引+1就是返回值
if (right - 1 >= 0 && arr[right-1] == target ){
return right-1;
}
//否则这个索引就是返回值
return right;
}
public static void main(String[] args) {
Comparable[] arr = {1,1,2,3,5,5,5,5,9};
System.out.println(floor(arr,0));
System.out.println(ceil(arr,0));
}
}
