type
status
date
slug
summary
tags
category
icon
password

1、概念

二分查找属于递归查找的一种,其主要思想是将一个有序数组,分为二分,进行递归,反复为之

2、实际应用

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

3、思路

notion image

4、代码实现

package com.qf.search; import java.util.ArrayList; import java.util.List; public class SeqSearch {    /**     * 二分查找     * @param args     */    public static void main(String[] args) {        //有序的数组        int[] arr={1,8, 10, 89, 1000,1234};        int i = seqSearch(arr, 0, arr.length - 1, 1000);        System.out.println("查找到的下标位置:"+i);   }    public static int seqSearch(int[] arr,int left,int right,int findValue){        //跳出循环        if (left>right){            return -1;       }        //找出中间的位置        int mid=(left+right)/2;        //中间的位置与要找的值进行对比        int midValue=arr[mid];        if (midValue<findValue){            //向右查找            return seqSearch(arr,mid+1,right,findValue);       }else if (midValue>findValue){            //向左查找            return seqSearch(arr,left,mid-1,findValue);       }else{            //相等,找到            return mid;       }   } }

5、思考题:

{1,8, 10, 89, 1000, 1000,1000,1000,1234} 当一个有序数组中,有多个相同的数值时,如何将所有的数值都查找到,比如这里的 1000.

6、优化实现

package com.qf.search; import java.util.ArrayList; import java.util.List; public class SeqSearch {    /**     * 二分查找     * @param args     */    public static void main(String[] args) {        //有序的数组        int[] arr={1,8, 10, 89, 1000, 1000,1000,1000,1234};        List<Integer> integerList = seqSearch2(arr, 0, arr.length - 1, 1000);        System.out.println("查找到的下标位置:"+integerList);   }    public static int seqSearch(int[] arr,int left,int right,int findValue){        if (left>right){            return -1;       }        //找出中间的位置        int mid=(left+right)/2;        //中间的位置与要找的值进行对比        int midValue=arr[mid];        if (midValue<findValue){            //向右查找            return seqSearch(arr,mid+1,right,findValue);       }else if (midValue>findValue){            //向左查找            return seqSearch(arr,left,mid-1,findValue);       }else{            //相等,找到            return mid;       }   }    public static List<Integer> seqSearch2(int[] arr, int left, int right, int findValue){        List<Integer> list=new ArrayList<>();        if (left>right){            return list;       }        //找出中间的位置        int mid=(left+right)/2;        //中间的位置与要找的值进行对比        int midValue=arr[mid];        if (midValue<findValue){            //向右查找            return seqSearch2(arr,mid+1,right,findValue);       }else if (midValue>findValue){            //向左查找            return seqSearch2(arr,left,mid-1,findValue);       }else{            //相等,找到            int temp=mid;            //向左查找与findValue相等的数值            while (true){                if (temp<left||arr[temp]!=findValue){                    break;               }                list.add(temp);                temp--;           }            //向右查找与findValue相等的数值            temp=mid+1;            while (true){                if (temp>right||arr[temp]!=findValue){                    break;               }                list.add(temp);                temp++;           }            return list;       }   } }
 
泛型二分查找算法(非递归)