对于一个有序数组,我们通常采用二分查找的方式来定位某一元素,请编写二分查找的算法,在数组中查找指定元素。
给定一个整数数组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; } };
//在普通二分查找多了一个限制条件,另外是按照增序写的,虽然题目中没有说。。。 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; } };
//递归求解 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); } };
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; } };
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; } }
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; }
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; } }
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; } }
//具体的想法在博客里,链接在回答最下方 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
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; } };
需要注意的是要保证一个元素出现多次,输出最左边的那个下标,因此不要一找到就停止二分查找
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;
}
};
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; } }
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); } }递归解法
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;
}
};
//该二分查找仅适用于升序的顺序表
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; } };
class BinarySearch { public: int getPos(vector<int> A, int n, int val) { int l=0,h=n-1,mid; bool flag=false; while(l<=h && !flag) { mid = (l+h)/2; if(A[mid]==val) flag = true; else if(A[mid]<val) l = mid+1; else h = mid-1; } if(flag && mid>=0){ while(mid>=0 && A[mid]==val) mid--; return mid+1; } return -1; } };