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

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);
}

}