欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

算法007:二分查找 请实现有重复数字的有序数组的二分查找,输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一

程序员文章站 2022-03-27 20:15:27
题目:二分查找 请实现有重复数字的有序数组的二分查找。输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。输入 5,4,[1,2,4,4,5]输出 3(从1开始的哦。不是index)思路:1.代码如下 BinSearch2 .java:package com.yuhl.right;/** * @author yuhl * @Date 2020/10/24 21:59 * @Classname BinSearch * @Description 二...
题目:
二分查找 请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。
输入 5,4,[1,2,4,4,5]
输出 3(从1开始的哦。不是index)

思路:

1.代码如下 BinSearch2 .java:

package com.yuhl.right;

/**
 * @author yuhl
 * @Date 2020/10/24 21:59
 * @Classname BinSearch
 * @Description 二分查找 请实现有重复数字的有序数组的二分查找。
 * 输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。
 * 输入 5,4,[1,2,4,4,5]
 * 输出 3
 */
public class BinSearch2 {
    public static void main(String[] args) {
        int[] a = {1,2,4,4,5};
        int res = findIt(5,3,a);
        System.out.println(res);
    }

    /**
     *
     * @param n 数组的长度
     * @param v 需要查找的值
     * @param a 已知数组
     * @return 所在的位置哦。不是index,是从1开始的位置哦
     */
    public static int findIt(int n, int v, int[] a) {
        //数组为空时返回值
        if(n==0)
            return 1;
        //定义区间左值、中值和右值
        int left=0;
        int right=n-1;
        int index;
        //当left和right重合时进行最后一次比较
        while(left<=right){
            index=(left+right)/2;
            if(a[index]>=v){//查找值小于等于中值时
                if(index==0||a[index-1]<v)//考虑到第一个值就是所求值的情况,防止index-1数组越界(短路运算)
                    return index+1;
                else
                    right=index-1;
            }else{//查找值大于中值时
                left=index+1;
            }
        }
        //未查找到在此处返回数组长度加1
        return n+1;
    }
}

2.执行结果:

"C:\Program Files\Java\jdk1.8.0_201\bin\java.exe" 
3

本文地址:https://blog.csdn.net/fsjwin/article/details/109267398

相关标签: 算法 java