Binary Search Algorithm

The binary search algorithm is one of the most commonly used algorithms in programming. The binary search algorithm is a divide and conquer algorithm that searches for a specific element in a sorted array.

Step 1:

Lets find the mid value element from the start and end values of a sorted array depending on their indexes.

int arr = new {4,7,12,45,50,53,65,76,77};
int target = 53;
int mid = (start + end) / 2;

but since the int value can be long enough we rewrite it as :

start+(end-start)/2=~ ( start+end) /2

If the target is smaller than the mid value we look towards left block of elements and skip the right side and find the mid again until start ≤=end and similarly if the target is greater than the mid value we consider only the right hand side of the mid value.

Step 2:

Once we have determined which side we want to go, we adjust our indexes accordingly. For example, if the target is smaller than mid, the end value get changed:

end = mid - 1;

Or if the target is larger than medium, the start value get changed:

start = mid + 1;

Step 3:

After doing the above steps till start ≤ end, if the element isn’t found in this loop return -1.

Lets see the complete code

public class Main{
    public static void main(String[] args) {
        int[] arr =new int[] {4,7,12,45,50,53,65,76,77};
        int target=53;
        int value= BinarySearch( arr, 53);
        System.out.println(value);
    }
    public static int BinarySearch(int arr[], int target){
        int start=0;
        int end=arr.length-1;
        int med = (start+end) / 2;
        while(start<=end){
            
            if (target>arr[med]){
                  start=med+1;
                  med =(start+end)/2;
              }
            else if(target<arr[med]){
                  end=med-1;
                  med =(start+end)/2;
              } else {
                  return med;
              }
          }  
          return -1;
        }
}

Complexity of Binary Search

We divide the array in half every time to find the target element. So the size under consideration is N. Every time we split the array into half, the size gets halved. Therefore, we can say that the size is N/2^i where i is the number of level. See diagram below. Now let’s assume that at kth level the problem is solved so at kth level the size becomes 1.

Therefore, the complexity is log N where N is number of elements in the array.

Agnostic Binary Search:

Binary search works both ways. When we have an array that is sorted but we don’t know whether its ascending sorted or descending sorted. We can still make binary search work.

eg: int arr[]=[3,3,3,37,8,17,90]

So under such situation compare the arr[0] with arr[n], so that you get to know the sort direction. On basis of that we can adjust our indexes. Here’s the complete code:

    public static void main(String[] args) {
        int[] arr = new int[]{4, 7, 12, 45, 50, 53, 65, 76, 77};
        int target = 53;
        int value = AgnosticBinarySearch(arr, 53);
        System.out.println(value);
    }

    public static int AgnosticBinarySearch(int arr[], int target) {
        int start = 0;
        int end = arr.length - 1;
        int med = (start + end) / 2;

        boolean isAsec = arr[start] < arr[end];

        while (start <= end) {
            if (arr[med] == target) {
                return med;
            }
            if (isAsec) {
                if (target < arr[med]) {
                    end = med - 1;
                } else {
                    start = med + 1;
                }
            } else {
                if (target > arr[med]) {
                    end = med - 1;
                } else {
                    start = med + 1;
                }
            }
            return -1;
        }
    }