查找算法介绍：
在java中，我们常用的查找有四种:
1.顺序(线性)查找
2. 二分查找/折半查找
3. 插值查找
4. 斐波那契查找
二分查找问题描述：
二分查找：
请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"
二分查找思路：
?注意：
用二分查找的情况下,序列必须是有序的。
代码：
package com.lzh.search;
import java.util.ArrayList;
import java.util.List;
/**
* 二分查找算法
*/
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1,8, 10, 89, 1000,1000, 1234};
int index = binartSearch(arr,0, arr.length-1, 1000);
System.out.println(index);
//多个数值
List<Integer> manyIndexList = binartSearchMany(arr,0, arr.length-1, 1000);
System.out.println(manyIndexList);
}
//二分查找算法(查找单个值)
public static int binartSearch(int[] arr,int left,int right,int value){
//如果左边的索引大于了右边的索引,就直接return
if (left > right){
return -1;
}
//中位数(分界点)当value==arr[mid]的时候,就代表找到了这个数
int mid = (left + right)/2;
//当value大于中位数时,就要往右递归查找
if (value > arr[mid]){
//向右递归查找
//从中位数的后一位开始(中位数的后一位算作最左边的索引)
return binartSearch(arr, mid+1, right, value);
}else if (value < arr[mid]){ //向左进行递归查找
//向左递归查找
//从中位数的前一位开始(中位数的前一位算作最右边的索引)
return binartSearch(arr, left, mid-1, value);
}else{
//如果上述条件都不满足,就代表arr[mid] == value了,代表找到这个数了,我们返回其下标
return mid;
}
}
//二分查找算法(查找多个值)
public static List<Integer> binartSearchMany(int[] arr, int left, int right, int value){
//如果左边的索引大于了右边的索引,就直接return
if (left > right){
return new ArrayList<Integer>();//如果 left > right 我们直接返回一个空集合
}
//中位数(分界点)当value==arr[mid]的时候,就代表找到了这个数
int mid = (left + right)/2;
//当value大于中位数时,就要往右递归查找
if (value > arr[mid]){
//向右递归查找
//从中位数的后一位开始(中位数的后一位算作最左边的索引)
return binartSearchMany(arr, mid+1, right, value);
}else if (value < arr[mid]){ //向左进行递归查找
//向左递归查找
//从中位数的前一位开始(中位数的前一位算作最右边的索引)
return binartSearchMany(arr, left, mid-1, value);
}else{
//如果上述条件都不满足,就代表arr[mid] == value了,代表找到这个数了,这是我们先不返回,看看这个数左右是否有相同的数
//有的话加入到集合中,没有的话,就返回集合
/** 思路分析
* 1. 在找到mid 索引值，不要马上返回
* 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
* 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
* 4. 将Arraylist返回
*/
int temp = mid - 1;//从中位数的前一位开始进行查找
//创建一个集合,用来存放这个值的下标
List<Integer> listIndex = new ArrayList<Integer>();
while(true){
//如果temp小于0,说明找到了最左边也没找到
//arr[temp] != value 说明没有我们要查找的数
//满足这两个条件中的任意一个都退出循环
if (temp < 0 || arr[temp] != value){
break;
}
//把下标放入到list集合中
listIndex.add(temp);
temp -= 1;//往左移
}
//把我们的中位数也加入到list集合中
listIndex.add(mid);
temp = mid +1;//从中位数的后一位开始进行查找
//往右查找
while(true){
//如果temp大于arr.length-1,说明找到了这个数组最右边也没找到
//arr[temp] != value 说明没有我们要查找的数
//满足这两个条件中的任意一个都退出循环
if (temp > arr.length-1 || arr[temp] != value){
break;
}
//把下标放入到list集合中
listIndex.add(temp);
temp += 1;//往左移
}
return listIndex;
}
}
}
?
?