首页 > 试题广场 >

二分查找

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

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

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

测试样例:
[1,3,5,7,9],5,3
返回:1
import java.util.*;

public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        // write code here
        int low=0,higth=n,res=-1;
        while (low != higth){
            int mid = (low + higth)/2;
            if (A[mid] > val){
                higth = mid;
            }else if (A[mid] < val){
                low = mid;
                if (res != -1){
                    break;
                }
            }else {
                res = mid;
                higth = mid;
            }
        }
        return res;
    }
}

发表于 2022-01-25 21:28:45 回复(0)
 这题其实可以分解成两部分。
1、找到存在的那个数。没找到返回-1;找到执行2.
2、以找到的那个数的坐标,作为结束节点。找第一个等于该值的坐标。(找第一个坏版本)
找的过程,以下面的模板作为二分法,注意边界的处理。
while(l<=r){
            int mid = l+(r-l)/2;
            if(A[mid]==val){
                same = mid;
                break;
            }
            if(A[mid]>val){
                r=mid-1;
            }else{
                l=mid+1;
            }
}


发表于 2022-01-12 10:07:47 回复(0)
import java.util.*;

public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        int left = 0;
        int right = n - 1;
        int mid = 0;
        while(left <= right){
            mid = (left + right) / 2;
            if(A[mid] > val){
                right = mid - 1;
            }else if(A[mid] < val){
                left = mid + 1;
            }else{
                while(mid >= 0){
                    if(A[mid] != val){
                        return mid + 1;
                    }else{
                        mid --;
                    }
                }
                return mid + 1;
            }
        }
        return -1;
    }
}

发表于 2020-04-30 09:26:21 回复(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)
import java.util.*;

public class BinarySearch 
{
    public int getPos(int[] A, int n, int val) 
    {
        return getIndex(A,0,A.length-1,val);
    }

    private int getIndex(int [] arr,int left,int right,int target)
    {
        if(left>right)//说明递归查找完整个数组,还没有找到
        {
            return -1;
        }
        int midIndex=(left+right)/2;
        int midValue=arr[midIndex];
        if(target>midValue)//如果你要找的数比中间的数大,就去右边找
        {
            return getIndex(arr,midIndex+1,right,target);
        }
        else if(target<midValue)//如果你要找的数比中间的数小,就去左边找
        {
            return getIndex(arr,left,midIndex-1,target);
        }
        else
        {
            while(midIndex>left&&arr[midIndex-1]==target)
            {
                midIndex=midIndex-1;
                return midIndex;
            }
            return midIndex;
        }

    }
}
发表于 2020-03-28 10:02:03 回复(0)
找到第一个比val小的数,res++就是第一个val出现的下标了,如果不是则证明val不存在
 public int getPos(int[] A, int n, int val) {
        int left=0;
        int right=n-1;
        int m;
        int res=-1;
        while(left<=right){
             m=(left+right)/2;
             if(A[m]<val){
                 res=m;
                 left=m+1;
             }else{
                 right=m-1;
             }
        }
        res++;
        if(res>=n||A[res]!=val) return -1;
        else return res;
    }
发表于 2018-08-24 23:59:11 回复(0)
//只说了找第一个,那就直接遍历一遍,找不到返回-1
public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
       for(int i = 0;i<A.length;i++){
       if(val == A[i])
           return i;
       }
        return-1;
    }
}
发表于 2018-08-18 16:39:14 回复(1)
import java.util.*;

public class BinarySearch {
    public int getPos(int[] a, int n, int value) {
        // write code here
        int middle;
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            middle = (left + right) / 2;
            if (a[middle] > value) {
                right = middle - 1;
            }
            else if (a[middle] < value) {
                left = middle + 1;
            }
            else {
                //return middle;
                //如果出现多次value,
                //遍历一下数组a获得第一个value的数组下标返回即可
                for (int i = 0; i < n; i++) {
                    if (a[i] == value) {
                        return i;
                    }
                }
            }
        }
        return -1;
    }
}
发表于 2018-05-26 11:36:05 回复(0)
import java.util.*;

public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        // write code here
        int start=0;
        int end=A.length;
        int mid=(start+end)/2;
        while(start<=end) {
            if(A[mid]==val) {
                return mid;
            }
            if(A[mid]<val) {
                start=mid+1;
            }else if(A[mid]>val){
                end=mid-1;
            }
            mid=(start+end)/2;
        }
        return -1;
    }
}

发表于 2018-01-31 11:45:31 回复(0)
二分查找看似简单,其实细节很多。返回第一次出现和最后一次出现,细节有很多。我简单标记一下,自己理解吧。
//指定值第一次出现
public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        int left = 0;
        int right = n-1;
        int center =(left+right)/2;
        while(left<right){
            if(A[center]>=val){//1、为什么这里取等放入
                right = center;
            }
            else{//2、为什么不在这边放置等于的情况
                left = center+1;
            }  
            //3、center赋值位置放这和放循环开始处什么区别
            //4、当取最后一次出现的位置,我这里一般改成(left+right+1)/2
            //5、当取最后一次出现的位置,除了4处修改,对于1、2取等和right left赋值都有些许变化
            center = (left+right)/2;
        }
        return A[center]==val?center:-1;
    }
}


编辑于 2017-12-10 22:19:23 回复(0)
二分法,当找到的时候 继续领end=mid,可以求出firstpos   另start=mid  可以求出endpostion 


public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        // write code here
        int start=0;
        int end=A.length-1;
        while(start+1<end){
            int mid = (start+end)/2;
            if(val==A[mid]){
                end=mid;
            }else if(val>A[mid]){
                start=mid;
            }else if(val<A[mid]){
                end=mid;
            }
        }
        
        if(A[start]==val){
            return start;
        }
        
        if(A[end]==val){
            return end;
        }
        
        return -1;
    }
}

发表于 2017-09-12 13:39:00 回复(0)
// Java 典型的 二分查找(递归做法)
    public int getPos(int[] A, int n, int val) {
        if (A == null || A.length <= 0)
            return -1;
        return getPos(A, 0, A.length-1, val);
    }

    private int getPos(int[] A, int low, int high, int val) {
        if (low > high)
            return -1;
        int mid = (low + high) >> 1;
        if (A[ mid ] == val && (mid == low || A[ mid - 1 ] != val))
            return mid;
        else if (A[ mid ] >= val)
            return getPos(A, low, mid - 1, val);
        else
            return getPos(A, mid + 1, high, val);

    }



// Java非递归 的二分查找
    public int getPos(int[] A, int n, int val) {
        if (A == null || A.length <= 0)
            return -1;
        int mid, low = 0, high = A.length - 1;
        while (low <= high) {
            mid = (low + high) >> 1;
            if (A[ mid ] == val && (mid == low || A[ mid-1 ] != val))
                return mid;
            else if (A[ mid ] >= val)
                high = mid - 1;
            else low = mid + 1;
        }
        return -1;
    } 

编辑于 2017-08-03 15:56:16 回复(0)
import java.util.*;

public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        int start = 0;
        int end = n - 1;
        boolean flag = false;
        while(!flag && start <= end) {
            int middle = start + ((end - start) >> 1);
            if(A[middle] == val) {
                flag = true;
            }
            else if(A[middle] > val) {
                end = middle - 1;
            } else {
                start = middle + 1;
            }
        }
        if (flag) {
            for(int index = 0;index < n;index++) {
                if(A[index] == val) {
                    return index;
                }
            }
        }
        return -1;
    }
}
注意这里当找到时不能直接返回,而是用一个标志位标志,然后再重新遍历一次数组找到第一次出现
的位置。

发表于 2017-07-22 19:12:42 回复(0)
public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        if(n<=0)
            return -1;
        int res=getk(0,n-1,A,val);
        return res;    
    }
    public int getk(int start ,int end ,int[] a,int val)
        {
        int mid=(start+end)/2;
        int num=a[mid];
    
        if(num>val)
            {
            end=mid;
            return getk(0,mid,a,val);
        }
        else if(num<val)
            {
            start=mid+1;
            return getk(mid+1,end,a,val);
        }
        else
            {
             if(mid==0)
                 return mid;
           for(int i=1;i<=mid;i++)
                {
                if(a[mid-i]==val)
                    return (mid-i);
                 else
                    return mid;
              }
        }
       return -1;
    }
}

发表于 2017-07-13 10:00:03 回复(0)
package HaoWeiLai;
import java.util.*;

public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
		int lo=0, hi=n;
        int target =search(A, lo, hi, val);
        if(target==n)
            return -1;
		return A[target] == val? target:-1;
    }
    public static int search(int[] A, int lo, int hi, int val){
    	int mid;
    	while(hi-lo>0){
    		mid = (lo+hi)>>1;
    		if(A[mid] < val){
    			lo = mid+1;
    		}else if ( val <=A[mid]){
    			hi = mid;
    		}
    	}
    	return lo;
    	
    }
}

编辑于 2017-06-11 00:19:12 回复(2)
import java.util.*;

public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        // write code here
        int begin = 0;
        int end = n-1;
        int mid = (begin+end)/2;
        while(begin<=end){
            if(val>A[mid]){
                begin = mid+1;
            }else if (val == A[mid]){
               if(mid>=1&&val==A[mid-1]){
                    end = mid-1;
                }else {
                    return mid;
                }
            }else {
                end = mid-1;
            }
            mid = (begin+end)/2;
        }
        return -1;
    }
}

发表于 2017-05-09 16:13:24 回复(0)
package com.ginto.practise010;

import java.util.Scanner;

public class BinarySearch {

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int[] A;
		int n;
		int val;
		System.out.print("输入数组大小:");
		n=scanner.nextInt();
		A=new int[n];
		System.out.print("输入数组元素:");
		for(int i=0;i<n;i++){
			A[i]=scanner.nextInt();
		}
		System.out.print("输入需要查找的元素:");
		val=scanner.nextInt();
		BinarySearch bs=new BinarySearch();
		System.out.println(bs.getPos(A, n, val));
	}

	 public int getPos(int[] A, int n, int val) {
	    int low=0;
	    int middle;
	    int high=A.length-1;
	    while(low<=high){
	    	middle=low+((high-low)>>1);
	    	
	    	if(A[middle]==val&&A[low]==A[middle]){
	    		return low;
	    	}else if(A[middle]==val){
	    		return middle;
	    	}else if(A[middle]>val){
	    		high=middle-1;
	    	}else{
	    		low=middle+1;
	    	}
	    }
	    return -1;
	 }
}

发表于 2017-05-08 22:00:29 回复(0)
import java.util.*;
 
public class Main {
public static int getPos(int[] A, int n, int val) {
              int start=0,end=n-1,midNum=-1;
              //Arrays.sort(A);
              while(start<=end){
                int mid=(start+end)/2;
                if(val==A[mid]){
                    midNum=mid;break;
                }
                else if(val>A[mid]){
                    start=mid+1;
                }
                else end=mid-1;
              }
              int K=midNum;
              if(K!=-1){
              for(int i=0;i<n;i++){
                 if(A[i]==A[K]){
                    midNum=i; break;
                 }
              }
            }
            return midNum;          
        }
}
发表于 2017-04-11 15:35:24 回复(0)
只考虑升序的解法如下,降序数组依次类推即可。
import java.util.*;

public class BinarySearch {
    public int getPos(int[] A, int n, int val) {
        // write code here
        int low = 0;
        int high = n;
        int mid = 0;
        while(low < high){
            mid = (low + high)/2;
            if(val <= A[mid]){
                high = mid;
            }else if(val > A[mid]){
                low = mid+1;
            }
        }
        if(val == A[low]){
            return low;
        }else{
            return -1;
        }
    }
}

编辑于 2017-03-31 14:54:20 回复(0)

问题信息

难度:
33条回答 46095浏览

热门推荐

通过挑战的用户

查看代码