首页 > 试题广场 >

二分查找

[编程题]二分查找

热度指数：64096 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一个有序数组，我们通常采用二分查找的方式来定位某一元素，请编写二分查找的算法，在数组中查找指定元素。

给定一个整数数组A及它的大小n，同时给定要查找的元素val，请返回它在数组中的位置(从0开始)，若不存在该元素，返回-1。若该元素出现多次，请返回第一次出现的位置。

测试样例：

[1,3,5,7,9],5,3

返回：1

算法知识视频讲解

cycleof

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)

~一念执着~

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

fight灬奋斗

//递归求解
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)

Python

华科平凡

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

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

编辑于 2017-09-12 13:50:53 回复(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;
        }
    }

编辑于 2015-09-20 23:04:30 回复(8)

webary

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)

青山崖野

注意：有序数组会有重复值，要求返回最开始的下标。

所以，通过二分法找到关键字之后，要查看它之前的数字，利用虚幻找到最早出现的位置。

发表于 2017-07-10 20:15:28 回复(0)

Fndoid

关键点应该是二分查到了之后不要停下来，继续让右指针左移（如果有下标更小的就能被查找到），直到左右下标都重合才退出即可

发表于 2016-12-20 21:37:03 回复(0)

Binn

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;

}

};

发表于 2016-03-30 12:52:03 回复(0)

pein531

二分搜索，但由于要考虑数组中存在多个等于目标值的元素时，需要返回目标值第一次出现的位置，所以在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)

Java

0xhzx

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)

cqu后起之秀

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)

2019眷顾我

需要注意的是要保证一个元素出现多次，输出最左边的那个下标，因此不要一找到就停止二分查找

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)

kestars

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)

mybaties

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)

C/C++

nbgao

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