# 二分查找

[编程题]二分查找
• 热度指数：62553 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
• 算法知识视频讲解

`[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;
}
};```

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

```//在普通二分查找多了一个限制条件，另外是按照增序写的，虽然题目中没有说。。。
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;
}
};
```

`return A.index(val) if val in A else -1`

Python one line solution. Life is short ,I use python.

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

《before:这道题不难，仅仅是在普通的二分查找的基础上加了一个限制条件：“ 若该元素出现多次，请返回第一次出现的位置。 ”，因此如果有相等的元素，第一次找到的可能不是第一次出现的元素，还要向前遍历，找到第一次出现的元素序号，然后返回即可》

class BinarySearch {
public:
int getPos(vector<int> A, int n, int val) {
// write code here
int lo=0,hi=n;
while(lo<hi){
int mi=(hi+lo)>>1;
if(val<=A[mi])hi=mi;
else  lo=mi+1;

}
return (A[lo]==val)?lo:-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));
}
}
————————————————

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

328条回答 46046浏览

## 通过挑战的用户

• 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，随时随地刷题