二分查找算法 | 程序员小舟

type

status

date

slug

summary

1、概念

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

2、实际应用

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

3、思路

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;
        }
    }
}