首页 > 试题广场 > 二分查找
[编程题]二分查找
  • 热度指数:57189 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

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

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

测试样例:
[1,3,5,7,9],5,3
返回:1
public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        // write code here
        if(n<=0 || A==null) return -1;
        int mid=0,L=0,R=n-1;
        while(L<R){
            mid = (L+R)/2;
            if(A[mid]>val){
                R=mid-1;
            }else if(A[mid]<val){
                L=mid+1;
            }else{
                
                R=mid;
            }
        }
        if(A[L]==val) return L;
        return -1;
    }
    
}

编辑于 2015-09-10 00:33:58 回复(23)
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、A数组中元素题目只说了是有序的,但没有说是递增的还是递减的
3、题目中要求用二分查找
以上三种情况就算是不考虑,程序依旧能够运行通过。测试用例给的太单一,根本没有考虑所有的情况。更不用说出现不合法的测试用例怎么办的问题了。
发表于 2016-08-23 17:59:31 回复(5)

感觉这道题有两个坑:

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)
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)
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)
class BinarySearch {
public:
    int getPos(vector<int> A, int n, int val) {
        int begin = 0,end = n-1;
        while(begin<end){
            int mid = (begin + end)>>1;
            if(A[mid]>=val)
                end = mid;
            else 
                begin = mid + 1;
        }
        return A[begin] == val? begin:-1;
    }
    
};

发表于 2017-03-29 19:39:44 回复(0)
关键点应该是二分查到了之后不要停下来,继续让右指针左移(如果有下标更小的就能被查找到),直到左右下标都重合才退出即可
发表于 2016-12-20 21:37:03 回复(0)
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)
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)