# Time Complexity

# Code Implementation

# Binary Search

Time complexity:

public class BinarySearch{
    public static int BinarySearch(int [] arr, int target){
        int a = 0;
        int b = arr.length - 1; //set up boundaries
        
        while (a <= b){

            int m = (a + b) / 2; // set up mid index

            if (arr[m] == target){
                return m; 
            }
            else if (arr[m] < target){
                a = m + 1; //move search range to the right
            }
            else {
                b = m - 1; // move search range to the left
            }
        }
        return -1;
    }
}

note: in this version, arr[b] never equals to the target.

public class BinarySearch{
    public static int BinarySearch(int [] arr, int target){
        int a = 0;
        int b = arr.length; //set up boundaries
        
        while (a < b){

            int m = (a + b) / 2; // set up mid index

            if (arr[m] == target){
                return m; 
            }
            else if (arr[m] < target){
                a = m + 1; //move search range to the right
            }
            else {
                b = m; // move search range to the left
            }
        }
        return -1;
    }
}