package com.qf.demo2;
import java.awt.List;
import java.util.ArrayList;
import javax.sound.midi.MidiChannel;
/*
 * 顺序查找:时间复杂度为o(n)
 * 二分查找  :前提条件是数组必须是有序的
 */
public class Test2 {

    public static void main(String[] args) {
          
         int[] a  = {2,1,4,9,5,3};
         int[] b = {3,5,8,34,90,234,657};
         System.out.println("用普通二分法查找3在数组中的位置"+(binarySearch2(b,3,0,6)+1)); 
         System.out.println("用普通二分法查找657在数组中的位置"+(binarySearch2(b,657,0,6)+1)); 
         System.out.println("用递归二分法查找3在数组中的位置"+(binarySearch(b,3,0,6)+1));  
         System.out.println("用递归二分法查找657在数组中的位置"+(binarySearch(b,657,0,6)+1));  
    }
    //顺序查找
    public static int find(int[] a,int b)
    {
           for(int i = 0;i<a.length;i++)
           {
               if(a[i]==b)
               {
                   return i;
               }
               
           }
           return -1;
    }
    //二分查找的递归实现
    public  static int binarySearch(int[] a,int b,int minIndex,int maxIndex)
    {
        if(minIndex<=maxIndex)
        {
            int middleindex = minIndex+(maxIndex-minIndex)/2;
            if(a[middleindex]==b){
                   return middleindex;          
            }  
            else        
                if(a[middleindex]>b){
                    return binarySearch(a, b, minIndex, middleindex-1);
                }
                else if(a[middleindex]<b){
                    return binarySearch(a, b, middleindex+1,maxIndex);
                }       
        }                   
        return -1;              
    }


//递归查找二分实现
import java.util.Scanner;
import java.util.function.BinaryOperator;

import javax.naming.BinaryRefAddr; 

    public class Main{
        
        public static void main(String[] args) {
       
            int[] a = new int[] {1,2,3,4,5,67,68};
             
            Scanner in  = new Scanner(System.in);
            int key = in.nextInt();
        //  System.out.println(binrescher(0, a.length-1, a, key));
            System.out.println(find(a, key, 0, a.length));  
            
        }
        
     public static int binrescher(int minIndex,int maxIndex,int[] s,int key)
     {
        if(minIndex<maxIndex)
        {
             int middIndex = (maxIndex+minIndex)/2+1;
             if(s[middIndex]==key)
             {
                 return middIndex;           
             }
             else
                 if(s[middIndex]<key)
                 {
                     minIndex = middIndex+1;
                    return binrescher(minIndex, maxIndex, s, key);
                 }
                 else
                     if(s[middIndex]>key)
                 {
                         maxIndex = middIndex-1;
                    return binrescher(minIndex, maxIndex, s, key);
                 }
             
        }
        else if(minIndex==maxIndex&&s[minIndex]==key)
        {
            return minIndex;
        }
        return -1;
     }
     public static int find(int[] a,int key,int min,int max){
            int mid = (min+max)/2;
            if(a[mid] == key){
                return mid;
            }else if(a[mid] > key){
                return find(a, key, min, mid-1);
            }else if(a[mid] < key){
                return find(a, key, mid+1, max);
            }
            return -1;
            
            
        }
 }





    //普通二分查找
    public static int binarySearch2(int[] a,int b,int minIndex,int maxIndex)
    {
        while(minIndex<=maxIndex) 
        {       
            if(minIndex<=maxIndex)
            {
                    int middIndex = (minIndex+maxIndex)/2;
                    if(a[middIndex]==b)
                    {
                            return middIndex;
                    }
                    else if(a[middIndex]>b)
                            maxIndex = middIndex-1;
                    else if(a[middIndex]<b)
                            minIndex = middIndex+1;
            }
        }
        return -1;
    }

}