Example analysis of binary search algorithm in Java

This article illustrates the binary search algorithm implemented in Java. Share with you for your reference. The details are as follows:

1. Premise: the premise of binary search is that the array to be searched must be sorted, and our implementation here defaults to ascending order

2. Principle: divide the array into three parts, namely, the median (the so-called median is the value in the middle of the array), the median, and the median; The value to be looked up is compared to the median of the array. If the value is less than the median, look before the median. If the value is greater than the median, look after the median. Then, in turn, there is a recursive process that continues to decompose the first half or the second half into three parts. Description may not be very clear, if you do not understand can go to the Internet. From the description you can see that this algorithm is suitable for recursive implementation, you can use recursion can use loop to achieve. So our implementation is divided into recursion and loop, and we can understand the algorithm according to the code

Implementation code:

public class BinarySearch {
 public static void main(String[] args){
 int searchArr[] = new int[1000000];
 for(int i=0;i<1000000;i++){
  searchArr[i]=i;
 }
   System.out.println(binSearch(searchArr,0,searchArr.length-1,99));
    System.out.println(binSearch(searchArr,99));
  }
//Recursive binary search
  public static int binSearch(int arr[], int start,int end,int sear){
    int mid = (end-start)/2 + start;
    if(sear==arr[mid]){
      return mid;
    }
    if(start>=end){
      return -1;
    }else if(sear < arr[mid]){
      return binSearch(arr,0,mid-1,sear);
    }else if(sear >arr[mid]){
      return binSearch(arr,mid+1,end,sear);
    }
    return -1;
  }
//Cyclic binary search
  public static int binSearch(int arr[],int key){
    int mid = arr.length/2;
    int start = 0;
    int end = arr.length-1;
    while(start<=end){
      mid = (end-start)/2+start;
      if(key ==arr[mid]){
        return mid;
      }else if(key <= arr[mid]){
        end = mid-1;
      }else if(key >=arr[mid]){
        start = mid+1;
      }
    }
    return -1;
  }

Efficiency comparison:

The efficiency of cyclic binary search algorithm is higher than that of recursive binary search algorithm

I hope this article has been helpful to your Java programming.