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

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。