二分查找在数组中应用的若干实例-向日葵屋

二分查找在数组中应用的若干实例

悠悠 2022-03-20 12:24 286阅读 0赞

在编程之美3.11一节中，我们遇到这么一个问题：找出一个有序（字典序）字符串数组中等于指定字符串的序号，如果有多个元素存在，则返回其中序号最大的。

对于这个问题，我们首先从非降序整形数组来看看如何实现，二分查找的思想很简单，就是不断判断数组中中间位置的元素与关键元素的大小关系，从而确定是在数组的左半部分继续查找还是在数组的右半部分继续查找。下面是Java实现二分查找的代码：

package com.part3;
//编程之美3.11 二分查找
public class BinarySearch {
    public static int location(int[] src,int key)
    {
        return location(src,0,src.length-1,key);
    }
    private static int location(int[] src,int start,int end,int key)
    {
        int s=start,e=end,m;//记录查找的首位置，末位置
        while(s<e-1)
        {
            m=s+(e-s)/2;
            if(src[m]<=key)
            {
                s=m;
            }
            else
            {
                e=m;
            }
        }
        if(src[e]==key)
            return e;
        else if(src[s]==key)
            return s;
        else
            return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] array={0,0,0,0,0,0,0};
        int key=0;
        System.out.println(key+" 在数组中的位置为："+location(array,key));
    }
}

测试结果如下：

0 在数组中的位置为：6

如果我们将测试数组更改为{ 0,1,1,2,3,3,3,3,4,5,6,7,7,7,9}，key=5，则我们得到的测试结果如下：

5 在数组中的位置为：9

从结果上看实现是正确的。

为了使所写的算法适用于所有实现Comparable接口的键，我们将程序修改如下：

package com.part3;
import java.util.Comparator;
//编程之美3.11 二分查找
public class BinarySearch<Key extends Comparable<Key>> {
    public int location(Key[] src,Key key)
    {
        return location(src,0,src.length-1,key);
    }
    private int location(Key[] src,int start,int end,Key key)
    {
        int s=start,e=end,m;
        while(s<e-1)
        {
            m=s+(e-s)/2;
            if(src[m].compareTo(key)<=0)
            {
                s=m;
            }
            else
            {
                e=m;
            }
        }
        if(src[e].equals(key))
            return e;
        else if(src[s].equals(key))
            return s;
        else
            return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Integer[] array={0,1,1,2,3,3,3,3,4,5,6,7,7,7,9};
        int key=5;
        String[] str={"is","is","majing","my","name","name","what","your",};
        String keystr="name";
        BinarySearch<Integer> intbs=new BinarySearch<Integer>();
        BinarySearch<String> strbs=new BinarySearch<String>();
        System.out.println(key+" 在数组中的位置为："+intbs.location(array,key));
        System.out.println(keystr+" 在数组中的位置为："+strbs.location(str,keystr));
    }
}

测试结果如下：

5 在数组中的位置为：9

name 在数组中的位置为：5

上面的算法中，要求返回关键字的最大序号，下面我们看一下另外一个问题。

对于一个给定的有序（非降序）数组arr，求任意一个i使得arr[i]=key，不存在则返回-1。

Java实现如下：

private int location(Key[] src,int start,int end,Key key)//返回任意一个等于关键字key的序号
    {
        int s=start,e=end,m;
        int flag;
        while(s<=e)
        {
            m=s+(e-s)/2;
            flag=src[m].compareTo(key);
            if(flag==0)
                return m;
            else if(flag>0)
                e=m-1;
            else
                s=m+1;
        }
        return -1;
    }

对于{0,1,1,3,3,3,3,4,4,5,6,7,7,7,9}数组测试结果如下：

3 在数组中的位置为：3

对于{“is”,”is”,”majing”,”my”,”name”,”name”,”what”,”your”}数组测试结果如下：

name 在数组中的位置为：5

与上面的算法相对应的，还存在下面一个问题：

对于一个给定的有序（非降序）数组arr，求最小的i使得arr[i]=key，不存在则返回-1。

Java实现如下所示：

private int location(Key[] src,int start,int end,Key key)
    {
        int s=start,e=end,m;
        while(s<e)
        {
            m=s+(e-s)/2;
            if(src[m].compareTo(key)<0)
            {
                s=m+1;
            }
            else
            {
                e=m;
            }
        }
        if(src[e].equals(key))
            return e;
        else
            return -1;
    }
测试代码：
public static void main(String[] args) {
        // TODO Auto-generated method stub
        Integer[] array={0,1,1,3,3,3,3,4,4,5,6,7,7,7,9};
        int key=3;
        String[] str={"is","is","majing","my","name","name","what","your"};
        String keystr="name";
        BinarySearch<Integer> intbs=new BinarySearch<Integer>();
        BinarySearch<String> strbs=new BinarySearch<String>();
        System.out.println(key+" 在数组中的位置为："+intbs.location(array,key));
        System.out.println(keystr+" 在数组中的位置为："+strbs.location(str,keystr));
    }