对于一个有序数组，我们通常采用二分查找的方式来定位某一元素，请编写二分查找的算法，在数组中查找指定元素。
给定一个整数数组A及它的大小n，同时给定要查找的元素val，请返回它在数组中的位置(从0开始)，若不存在该元素，返回-1。若该元素出现多次，请返回第一次出现的位置。
测试样例：
[1,3,5,7,9],5,3
返回：1
[编程题]二分查找
class BinarySearch {
public:
int getPos(vector<int> A, int n, int val) {
if( n == 0 || A.size() == 0 )//异常处理
return -1;
int lift = 0,right = n-1,mid = 0;
while( lift <= right ){
mid = (right + lift)/2;
if( A[mid] > val )
right = mid - 1;
else if( A[mid] < val )
lift = mid + 1;
else{
while( mid>=0 && A[mid] == val )//找到后向前遍历看是否有相同
mid--;
return mid+1;
}
}
return -1;
}
};
发表于 2017-07-10 18:11:08
回复(1)
感觉这道题有两个坑：
1 数组升序还是降序不能确定
2 折半查找到位置之后还需要向前依次索引找出最靠前的
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
if(A==null || n==0){
return -1;
}
int low = 0;
int high = n;
// write code here
//降序
if(A[0] > A[n-1]){
while(low <= high){
int middle = (low + high)/2;
if(A[middle] == val){
return findFirstPosition(A,middle,val);
}else if(A[middle] > val){
low = middle + 1;
}else{
high = middle - 1;
}
}
}
//升序
if(A[0] < A[n-1]){
while(low <= high){
int middle = (low + high)/2;
if(A[middle] == val){
return findFirstPosition(A,middle,val);
}else if(A[middle] > val){
high = middle - 1;
}else{
low = middle + 1;
}
}
}
if(A[0] == val){
return 0;
}
return -1;
}
private int findFirstPosition(int[] A,int middle,int val){
int position = middle;
while(position >=0 && A[position] == val){
position--;
}
return position+1;
}
}
编辑于 2017-02-21 11:45:45
回复(0)
//在普通二分查找多了一个限制条件，另外是按照增序写的，虽然题目中没有说。。。
class BinarySearch {
public:
int getPos(vector<int> A, int n, int val) {
int start=0,end=n-1;
int mid;
while(start<=end){
mid=(start+end)/2;
if(A[mid]==val&&(mid==0||A[mid-1]<A[mid]))//找到了目标元素并且还是第一次出现的就返回结果
return mid;
else if((A[mid]==val&&A[mid-1]==A[mid])||val<A[mid])//找到了目标元素并且不是第一次出现的或者目标元素小于中间元素继续向左走
end=mid-1;
else
start=mid+1;
}
return -1;
}
};
发表于 2017-07-03 15:03:41
回复(0)
//递归求解
class BinarySearch {
public:
int getPos(vector<int> A,int begin,int end,int val){
int mid=(begin+end)/2;
if(A[mid]==val){
while(mid>begin&&A[mid-1]==val)
mid--;
return mid;
}else if(A[mid]>val){
return getPos(A,begin,mid-1,val);
}else{
return getPos(A,mid+1,end,val);
}
}
int getPos(vector<int> A, int n, int val) {
if(n<1)
return -1;
return getPos(A,0,n-1,val);
}
};
发表于 2016-08-16 15:37:35
回复(0)
class BinarySearch {
public:
int getPos(vector<int> A, int n, int val) {
// write code here
///PS:主要是比折半查找多了一步：若该元素出现多次，请返回第一次出现的位置。
int low =0,high =n-1;
int mid = -1;
bool flag = false;
while(!flag && low<=high){
mid = (low+high)/2;
if(val == A[mid])
flag = true;
else if(A[mid] < val)
low = mid+1;
else
high = mid-1;
}
//下面找出现多次的时候的第一次出现的位置
if(flag && mid > -1){
while(mid>=0 && A[--mid] == val);
return mid+1;
}
return -1;
}
};
发表于 2016-06-28 07:51:02
回复(11)
int getPos(vector<int> A, int n, int val) {
// write code here
if(n<=0) {
return -1;
}
int start = 0;
int end = n-1;
int mid;
int result = 0;
while(start <= end) {
mid = (start + end) / 2;
if(A[mid] < val) {
start = mid + 1;
} else if(A[mid] >= val) {
end = mid -1;
}
result = start;
}
if(A[result] == val) {
return result;
} else {
return -1;
}
}
编辑于 2015-09-20 23:04:30
回复(8)
int getPos(vector<int> A, size_t len, int value) {
int low = 0, high = len-1, mid;
if(arr[low]>value || arr[high]<value) //不在范围内
return -1;
while(low <= high) {
mid = low + ((high-low)>>1);
if(value<=arr[mid])
high = mid-1;
else
low = mid+1;
}
return (value-arr[low]<1e-6 && arr[low]-value<1e-6)?low:-1;
}
根据下面的回复，我进行了部分修改，这样就可以实现完全二分查找，定位到第一次出现的位置。
《before:这道题不难，仅仅是在普通的二分查找的基础上加了一个限制条件：“ 若该元素出现多次，请返回第一次出现的位置。
”，因此如果有相等的元素，第一次找到的可能不是第一次出现的元素，还要向前遍历，找到第一次出现的元素序号，然后返回即可》
编辑于 2015-09-11 01:25:04
回复(7)
二分搜索，但由于要考虑数组中存在多个等于目标值的元素时，需要返回目标值第一次出现的位置，所以在A[mid]=val时，需要收缩右边界right=mid(不是right=mid-1，因为mid可能就是第一个出现的位置)。
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
// write code here
int left = 0, right = n - 1;
while(left < right){
int mid = left + (right - left) / 2;
if(A[mid] > val)
right = mid - 1;
else if(A[mid] < val)
left = mid + 1;
else
right = mid;
}
return A[left] == val? left: -1;
}
}
编辑于 2021-04-10 21:19:49
回复(0)
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
int first = 0, last = n,mid;//n
while(first < last){
if(A[0]==val)
//经过观察，这种写法仅在第一个位置是val时输出错误，所以单独处理
return 0;
mid = first + (last-first)/2;
if(A[mid]<val){
first = mid + 1;
}
else if(A[mid]==val){
return mid;
}
else
last = mid;
}
return -1;
}
}
发表于 2020-04-29 21:28:26
回复(0)
//具体的想法在博客里，链接在回答最下方
public class BinarySearch {
//递归版本
public static void binarySearch(int[] array,int target){
int left=0;
int right=array.length-1;
System.out.println(rec_binarySearch1(array, left, right, target));
}
/* 这里输出的时候因为要满足题意若该元素出现多次，请返回第一次出现的位置。
所以我们要进行判断
*/
public static int rec_binarySearch1(int[] array,int left,int right,int target){
int mid=(left+right)>>1;
if(left>right){
return -1;
}
//第一种：结合它是有序数组排除特殊特殊情况进行判断：这里可能会不太好理解
if(array[mid]==target&&(mid==left||array[mid-1]!=target)){
//mid==left结合只有两个一样的数据来想
//array[mid-1]!=target 结合数组是有序的来想
return mid;
}
if(array[mid]>=target){ //这里是 >= 因为如果不写=的话上边的那个if判断没成功就只能返回-1了
return rec_binarySearch1(array,left,mid-1,target);
}else if(array[mid]<target) {
return rec_binarySearch1(array,mid+1,right,target);
}
return -1;
}
public static int rec_binarySearch2(int[] array,int left,int right,int target){
int mid=(left+right)>>1;
if(left>right){
return -1;
}
if(array[mid]>target){ //这里是 > 因为等于的情况下边会进行处理
return rec_binarySearch2(array,left,mid-1,target);
}else if(array[mid]<target) {
return rec_binarySearch2(array,mid+1,right,target);
}
//第二种：如果出现多次target，遍历一下数组a获得第一个value的数组下标返回即可
for(int i=0;i<array.length;i++){
if(array[i]==target){
return i;
}
}
return -1;
}
//迭代版本
public static int ite_binarySearch(int[] array,int target){
int left=0;
int right=array.length-1;
while(left<=right){ //这里要有= ,否则（如果恰好这里有我们要返回的数据），错过了left==right这里会直接返回-1
int mid=(left+right)>>1;
if(array[mid]==target&&(mid==left||array[mid-1]!=target)){
return mid;
}else if(array[mid]>=target){
right=mid-1; //说明想要的数在array[mid]的左边（array是个升序数组）
}else{
left=mid+1; //说明想要的数在array[mid]的右边（array是个升序数组）
}
}
return -1;
}
public static void main(String[] args) {
int[] array={4,4,10,21};
//binarySearch(array,4);
System.out.println(ite_binarySearch(array,4));
}
}
————————————————
版权声明：本文为CSDN博主「峰回路转」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44840148/article/details/105422759
发表于 2020-04-09 23:59:19
回复(0)
class BinarySearch {
public:
int getPos(vector<int> A, int n, int val) {
int l = -1;
int r = n;
while (1 + l != r) {
int i = (l + r) / 2;
if (val > A[i]) l = i;
if (val ==A[i]) {
while (i > 0 && A[i - 1] == A[i]) {
//当找到了的时候再判断一下它前面有几个和它相等的数 有几个就减几再返回
i--;
}
return i;
}
if (val < A[i]) r = i;
}
return -1;
}
};
编辑于 2019-07-19 20:18:42
回复(0)
需要注意的是要保证一个元素出现多次，输出最左边的那个下标，因此不要一找到就停止二分查找
class BinarySearch {
public:
int getPos(vector<int> A, int n, int val) {
// write code here
int start=0,right=n-1,middle;
int res=-1;
while(start<=right){
middle=(start+right)/2;
if(A[middle]==val){
if(res!=-1)
res=min(res,middle);
else
res=middle;
right=middle-1;
}else if(A[middle]<val){
start=middle+1;
}else
right=middle-1;
}
return res;
}
};
发表于 2018-11-02 09:56:02
回复(0)
import java.util.*;
public class BinarySearch {
public int getPos(int[] A, int n, int val) {
//Arrays.sort(A);
int L=0;
int R=n-1;
int mid=0;
int result=-1;
while(L<=R){
mid=(L+R)/2;
if(A[mid]>val){
R=mid-1;
}else if(A[mid]<val){
L=mid+1;
}else {
result=mid;
R=mid-1;
}
}
return result;
}
}
发表于 2018-10-08 22:49:29
回复(0)
import java.util.*;
public class BinarySearch {
public static int getPos(int[] A, int n, int val) {
// write code here
int a = Search(A,0,n-1,val);
for(int i = 0 ; i < a; i++)
if(A[i] == val)return i;
return a;
}
public static int Search(int[] A,int L,int R,int val){
int mid = (L + R) / 2;
if(A[mid] == val)return mid;
if(A[mid] != val && R-L <= 1){
if(A[mid+1] == val)return mid+1;
else return -1;
}
if(A[mid]>val)return Search(A,L,mid,val);
else return Search(A,mid+1,R,val);
}
}
递归解法
发表于 2018-08-25 14:53:06
回复(0)
class BinarySearch {
public:
int getPos(vector<int> A, int n, int val) {
// write code here
int low = 0,high = n,mid;
while(low <= high) {
mid = (high + low)/2;
if(A[mid] == val) {
return mid;
}
else if(A[mid] > val) {
high = mid - 1;
}
else{
low = mid + 1;
}
}
return-1;
}
};
//该二分查找仅适用于升序的顺序表
编辑于 2018-06-20 10:07:45
回复(0)
class BinarySearch {
public:
int getPos(vector<int> A, int n, int val) {
// write code here
int first=0,last=n-1;
while(first<=last)
{
int mid=(first+last)/2;
if(A[mid]==val)
{
if(mid>=1)
{
while(A[mid]==A[mid-1])
mid--;
}
return mid;
}
else if(A[mid]<val)
first=mid+1;
else
last=mid-1;
}
return -1;
}
};
发表于 2018-01-19 21:51:14
回复(0)
问题信息
难度：
328条回答
291收藏
45995浏览
通过挑战的用户
查看代码-
2023-01-11 17:21:16 -
2022-11-07 20:15:00
-
2022-11-01 21:33:42 -
2022-10-12 16:33:22
-
2022-10-12 15:26:54
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
