二分查找算法思想及代码

快来打我* 2022-12-12 12:24 188阅读 0赞

## 二分查找 算法 ##

题目：  
请实现有重复数字的有序数组的二分查找。  
输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。

示例1
    输入
    5,4,[1,2,4,4,5]
    输出
    3

思想：二分查找法 首先要 定义 两个指针 标记左右，然后用mid所指的位置与关键字比较。若小于关键字，则在其右侧继续二分查找，若大于等于关键字，且其左临元素也大于等于改关键字，则继续在mid的左侧二分查找，否则输出mid+1,若遍历后不存在这样的值，输出n+1。

public class Solution{
        
       public class upper_bound_(int n, int v, int[] a){
        
          int i=0;
          int j=n-1;
          int mid=(i+j)/2;
          while(i<j){
        
           if(a[mid]<v){
        
             i=mid+1;
             mid=(i+j)/2;
           }  else if(mid>0&&a[mid-1]>=v){
        
                j=mid-1;
                  mid=(i+j)/2;  
           }else{
        
                  return min+1;
           }
                  return n+1;
    }
       }
    }

递归实现

ublic class BinarySearch {
        
        public static  void main(String[] args){
        
            int[] a={
        1,2,3,4,5,6,7,8,9};
            int key=7;
            System.out.println("查找到"+ chooseResult(a,key,0,a.length-1));
        }
        public static int chooseResult(int[] a,int key,int low,int high){
        
            if(low>high)return -1;
            int mid=low+(high-low)/2;
            if(a[mid]>key){
        
               return chooseResult(a,key,low,mid-1);
            }else if(a[mid]<key){
        
               return chooseResult(a,key,mid+1,high);
            }
            return mid;
        }
    
    }

非递归实现

public static int chooseResult(int[] a,int key){
        
            int low=0;
            int high=a.length-1;
            while (low<=high){
        
                int mid=low+(high-low)/2;
                if(a[mid]>key){
        
                    high=mid-1;
                }else if(a[mid]<key){
        
                    low=mid+1;
                }else{
        
                    return mid;
                }
            }
            return -1;
        }