二分查找

前提条件

我们的二分查找必须是在有序数组中查找

无论是从小到大还是从大到小

题目

请对一个有序数组进行二分查找{1, 8,10,89,1000,1234}，输入一个数
看看该数组是否在此数，姐出下标，如果没有就提示没有这个数”。

思路

我们这次的二分查找会用到递归的思想，当然也有非递归的方式，我是分开来学习了

1.首先确定数组的中间下标mid mid = (left+ right)/2

2.让需要查找的数findValue和我们的arr[mid]比较

​ 如果findValue>arr[mid]，往右边递归找

​ 如果findValue<arr[mid]，向左边递归查找

​ 如果正好找到就返回

那我们的递归出口(结束条件)是什么

1.找到了，直接返回退出了

2.递归万整个数组，没有找到findValue，也需要结束递归时，当我们的left>right就代表要结束了

代码

//二分查找
//@author 王
public class BinarySearch {
    

	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
		int arr[] = {
    1,8,10,89,1000,1234};//必须是有序数组
		int resultIndex = binarySearch(arr, 0, arr.length -1, 1234);
		System.out.println(resultIndex);
	}
	/**
	 * 
	 * @param arr			数组
	 * @param left			左边索引
	 * @param right			右边索引
	 * @param findValue		需要找的数字，找到返回下标，未找到返回-1
	 * @return
	 */
	//二分查找算法
	public static int binarySearch(int[] arr,int left,int right,int findValue) {
    
		int mid = (left+right)/2;
		int midValue = arr[mid];
		
		if(findValue >midValue){
    
			//向右递归
			return binarySearch(arr, mid+1, right, findValue);
		}else if(findValue < midValue){
    
			//向左递归
			return binarySearch(arr, left, mid-1, findValue);
		}else{
    
			return mid;
		}
	}

}

我们很容易发现这其中的问题，我们的递归存在问题，如果我们找一个不存在的数救会报错，这个错误是死递归造成的错误

Exception in thread "main" java.lang.StackOverflowError
	at 查找算法.BinarySearch.binarySearch(BinarySearch.java:27)

那我们就得来写出这个递归的结束出口

改进

//二分查找
//@author 王
public class BinarySearch {
    

	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
		int arr[] = {
    1,8,10,89,1000,1234};//必须是有序数组
		int resultIndex = binarySearch(arr, 0, arr.length -1, 123);
		if(resultIndex != -1){
    
			System.out.println(resultIndex);
		}else{
    
			System.out.println("没有找到这个数字");
		}
	}
	/**
	 * 
	 * @param arr			数组
	 * @param left			左边索引
	 * @param right			右边索引
	 * @param findValue		需要找的数字，找到返回下标，未找到返回-1
	 * @return
	 */
	//二分查找算法
	public static int binarySearch(int[] arr,int left,int right,int findValue) {
    
		if(left > right){
    
			return -1;
		}
		int mid = (left+right)/2;
		int midValue = arr[mid];
		if(findValue >midValue){
    
			//向右递归
			return binarySearch(arr, mid+1, right, findValue);
		}else if(findValue < midValue){
    
			//向左递归
			return binarySearch(arr, left, mid-1, findValue);
		}else{
    
			return mid;
		}
	}

}

我们再来扩充一点，也是老师的课后习题
{1,8,10,89,1000,1000，1000，1234} 当一个有序数组中,有多个相同的数值时，如何将所有的数值都查找到，比如这里的1000.

思路跟我上一个学的差不多，我们可以采用一个集合来存储我们的索引值，返回我们的集合

代码

public class BinarySearch {
    

	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
		int arr[] = {
    1,8,10,89,1000,1000,1000,1234};//必须是有序数组
		ArrayList<Integer> resultIndex = binarySearch2(arr, 0, arr.length -1, 1000);
		if(resultIndex.size() == 0){
    
			System.out.println("没有找到这个数字");
		}else{
    
			System.out.println(resultIndex);
		}
	}
    public static ArrayList<Integer> binarySearch2(int[] arr,int left,int right,int findValue) {
    
			if(left > right){
    
				return new ArrayList<Integer>();
			}
			int mid = (left+right)/2;
			int midValue = arr[mid];
			if(findValue >midValue){
    
				//向右递归
				return binarySearch2(arr, mid+1, right, findValue);
			}else if(findValue < midValue){
    
				//向左递归
				return binarySearch2(arr, left, mid-1, findValue);
			}else{
    
				ArrayList<Integer> list = new ArrayList<Integer>();
				int temp = mid -1;
				//向左边扫描
				while(true){
    
					if(temp < 0 || arr[temp] != findValue){
    
						//退出
						break;
					}else{
    
						//否则就将temp放到集合中
						list.add(temp);
						temp -= 1;//temp左移
					}
				}
				list.add(mid);
				//向右扫描
				temp = mid +1;
				while(true){
    
					if(temp > arr.length - 1 || arr[temp] != findValue){
    
						//退出
						break;
					}else{
    
						//否则就将temp放到集合中
						list.add(temp);
						temp += 1;//temp左移
					}
				}
				return list;
			}
		}
}