Binary Search

PHOTO EMBED

Tue Feb 08 2022 13:03:48 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #binarysearch #recursivesolution #iterativesolution

// Iterative Solution : Time Complexity : O(LogN),  Aux. Space : O(1)

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int bSearch(int arr[], int n, int x)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(arr[mid] == x)
				return mid;

			else if(arr[mid] > x)
				high = mid - 1;

			else
				low = mid + 1;
		}

		return -1;
	}

	public static void main(String args[]) 
	{
        int arr[] = {10, 20, 30, 40, 50, 60}, n = 6;

		int x = 25;
    
        System.out.println(bSearch(arr, n, x));  // Output : -1
		
    } 

}





// Recursive Solution : Time Complexity : O(LogN),  Aux. Space : O(logN)

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int bSearch(int arr[], int low, int high, int x)
	{
		if(low > high)
			return -1;

		int mid = (low + high) / 2;

		if(arr[mid] == x)
			return mid;

		else if(arr[mid] > x)
			return bSearch(arr, low, mid - 1, x);

		else
			return bSearch(arr, mid + 1, high, x);
	}

	public static void main(String args[]) 
	{
        int arr[] = {10, 20, 30, 40, 50, 60, 70}, n = 7;

		int x = 20;

        System.out.println(bSearch(arr, 0, n - 1, x));  // Output : 1
    } 
}
content_copyCOPY