DSA-lab6(b)-Binary_Search

import java.util.Scanner;

/**
 * Binary Search Program
 * ----------------------
 * Works only on sorted arrays
 * Uses divide and conquer approach
 * 
 * Time Complexity:
 * - Best Case: O(1)
 * - Worst Case: O(log n)
 */
public class BinarySearch {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter number of elements: ");
        int n = sc.nextInt();
        int[] arr = new int[n];
        System.out.println("Enter sorted elements:");
        for (int i=0; i<n; i++) arr[i] = sc.nextInt();
        
        System.out.print("Enter element to search: ");
        int key = sc.nextInt();
        
        int pos = binarySearch(arr, key);
        
        if (pos == -1) System.out.println("Element not found");
        else System.out.println("Element found at position: " + (pos + 1));
        sc.close();
    }
    
    public static int binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] == key) return mid;
            else if (arr[mid] < key) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }
}