1.4.10

发布时间：2020-12-14 04:48:47 所属栏目：大数据来源：网络整理

导读：question: Modify binary search so that it always returns the element with the smallest index that mathes the search element (and still guarantees logarithmic running time). answer: //注意二分查找一定要是有序数组！！！(我搞忘记了，然后怎么

question:

Modify binary search so that it always returns the element with the smallest index that mathes the search element (and still guarantees logarithmic running time).

answer:

//注意二分查找一定要是有序数组！！！(我搞忘记了，然后怎么都查不出错QAQ)

import edu.princeton.cs.algs4.*;

public class BinarySearch
{
    public static int Rank(int key,int[]a,int lo,int hi)
    {
        if(lo > hi)
            return -1;
        int mid = lo + (hi - lo)/2;
        if(a[mid] == key) 
        {
            int min = Rank(key,a,lo,mid-1);
            if(min != -1)
                return min;
            return mid;
        }
        else if(a[mid] > key)
            return Rank(key,mid-1);
        else
            return Rank(key,mid+1,hi);
    }

    
    public static void main(String[] args)
    {
        int a[] = {0,1,2,4,5,6,8,9,10};//二分查找必须是有序数组！！！
        int key = 1;
        int ans = Rank(key,a.length-1);
        StdOut.println(ans);
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!