算法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