鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > java > >

#yyds干货盘点# 解决名企真题:二分查找

来源:互联网 作者:佚名 时间:2022-07-19 11:00
1.简述: 描述 对于一个有序数组,我们通常采用二分查找的方式来定位某一元素,请编写二分查找的算法,在数组中查找指定元素。 给定一个整数数组A及它的大小n,同时给定要查找的

1.简述:

描述

对于一个有序数组,我们通常采用二分查找的方式来定位某一元素,请编写二分查找的算法,在数组中查找指定元素。

给定一个整数数组A及它的大小n,同时给定要查找的元素val,请返回它在数组中的位置(从0开始),若不存在该元素,返回-1。若该元素出现多次,请返回第一次出现的位置。

测试样例:

[1,3,5,7,9],5,3返回:1

2.代码实现:

import java.util.*;

public class BinarySearch {
public int getPos(int[] A, int n, int val) {
// write code here
int l = 0; int r = n;
return getMid(A,l,r,val);
}

private int getMid(int[] A,int l,int r,int val){
int mid = (l+r)/2;

if(A[mid] < val){
l = mid;
}
//值相等且为首位(没有更早出现的可能)或者上一位与当前位值不等(因为是有序,只要不等,那么此处就是首次出现的位置了)
if(A[mid] == val && (mid == 0 || A[mid]!=A[mid-1])){
return mid;
}
//右边的或条件不能放到当前值小于val的条件判断中(因为有序的先决条件是从小到大,首次出现又是要求往前判断,所以或语句放在这个位置)
if(A[mid]>val || (A[mid] == val && A[mid]==A[mid-1])){
r = mid;
}
//如果二分到左右点相邻仍未找到这个val,则说明不存在。
if(r-l==1 && A[r]!=val && A[l]!=val){
return -1;
}
return getMid(A,l,r,val);
}

}
上一篇:vec2d
下一篇:没有了
网友评论
<