# Searching

```// 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
}
}```
```// Efficient Code (Iterative)

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

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

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

if(x > arr[mid])
low = mid + 1;

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

else
{
if(mid == 0 || arr[mid - 1] != arr[mid])
return mid;

else
high = mid - 1;
}

}
return -1;
}

public static void main(String args[])
{
int arr[] = {5, 10, 10, 10, 20}, n = 5;

int x = 10;

System.out.println(firstOcc(arr, n, x));   // OUTPUT : 1
}
}

// Efficient Code (Recursive)

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

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

int mid = (low + high) / 2;

if(x > arr[mid])
return firstOcc(arr, mid + 1, high, x);

else if(x < arr[mid])
return firstOcc(arr, low, mid - 1, x);

else
{
if(mid == 0 || arr[mid - 1] != arr[mid])
return mid;

else
return firstOcc(arr, low, mid - 1, x);
}
}

public static void main(String args[])
{
int arr[] = {5, 10, 10, 15, 20, 20, 20}, n = 7;

int x = 20;

System.out.println(firstOcc(arr, 0, n - 1, x));   // OUTPUT : 4
}
}

// Naive Code

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

class GFG
{
static int firstOccurrence(int arr[], int n, int x)
{
for(int i = 0; i < n; i++)
if(arr[i] == x)
return i;

return -1;
}

public static void main(String args[])
{
int arr[] = {5, 10, 10, 15, 15}, n = 5;

int x = 15;

System.out.println(firstOccurrence(arr, n, x));   // OUTPUT : 3
}
}
```
```// Iterative Code

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

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

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

if(x > arr[mid])
low = mid + 1;

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

else
{
if(mid == n - 1 || arr[mid + 1] != arr[mid])
return mid;

else
low = mid + 1;
}

}

return -1;
}

public static void main(String args[])
{
int arr[] = {5, 10, 10, 10, 10, 20, 20}, n = 7;

int x = 10;

System.out.println(lastOcc(arr, n, x));   // OUTPUT : 4
}

}

// Recursive Code

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

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

int mid = (low + high) / 2;

if(x > arr[mid])
return lastOcc(arr, mid + 1, high, x, n);

else if(x < arr[mid])
return lastOcc(arr, low, mid - 1, x, n);

else
{
if(mid == n - 1 || arr[mid + 1] != arr[mid])
return mid;

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

public static void main(String args[])
{
int arr[] = {5, 10, 10, 10, 10, 20, 20}, n = 7;

int x = 10;

System.out.println(lastOcc(arr, 0, n - 1, x, n));   // OUTPUT : 4
}

}```
```import java.util.*;
import java.io.*;

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

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

if(x > arr[mid])
low = mid + 1;

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

else
{
if(mid == 0 || arr[mid - 1] != arr[mid])
return mid;

else
high = mid - 1;
}

}

return -1;
}

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

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

if(x > arr[mid])
low = mid + 1;

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

else
{
if(mid == n - 1 || arr[mid + 1] != arr[mid])
return mid;

else
low = mid + 1;
}

}

return -1;
}

static int countOcc(int arr[], int n, int x)
{
int first = firstOcc(arr, n, x);

if(first == -1)
return 0;
else
return lastOcc(arr, n, x) - first + 1;
}

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

int x = 20;

System.out.println(countOcc(arr, n, x));   // OUTPUT : 3

}

}```
```import java.util.*;
import java.io.*;

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

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

if(arr[mid] == 0)
low = mid + 1;
else
{
if(mid == 0 || arr[mid - 1] == 0)
return (n - mid);
else
high = mid -1;
}
}

return 0;
}

public static void main(String args[])
{
int arr[] = {0, 0, 1, 1, 1, 1}, n = 6;

System.out.println(countOnes(arr, n));   // OUTPUT : 4

}

}```
```// Efficient Code

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

class GFG
{
static int sqRootFloor(int x)
{
int low = 1, high = x, ans = -1;

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

int mSq = mid * mid;

if(mSq == x)
return mid;
else if(mSq > x)
high = mid - 1;
else
{
low = mid + 1;
ans = mid;
}
}

return ans;
}

public static void main(String args[])
{

System.out.println(sqRootFloor(10));

}

}

// Naive Code

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

class GFG
{
static int sqRootFloor(int x)
{
int i = 1;

while(i * i <= x)
i++;

return i - 1;
}

public static void main(String args[])
{

System.out.println(sqRootFloor(15));

}

}
```
```// Efficient Code

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);
}

static int search(int arr[], int x)
{
if(arr[0] == x) return 0;

int i = 1;

while(arr[i] < x)
i = i * 2;

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

return bSearch(arr, i / 2 + 1, i - 1, x);
}

public static void main(String args[])
{
int arr[] = {1, 2, 3, 40, 50};

int x = 4;

System.out.println(search(arr, x));     // OUTPUT : -1
}

}

// Naive Code

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

class GFG
{
static int search(int arr[], int x)
{
int i = 0;

while(true)
{
if(arr[i] == x) return i;

if(arr[i] > x) return -1;

i++;
}
}

public static void main(String args[])
{
int arr[] = {1, 2, 3, 5, 5};

int x = 4;

System.out.println(search(arr, x));     // OUTPUT : -1
}

}```
```// Efficient Code

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

class GFG
{

static int search(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;
if(arr[low] < arr[mid])
{
if(x >= arr[low] && x < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
else
{
if(x > arr[mid] && x <= arr[high])
low = mid + 1;
else
high = mid - 1;
}
}

return -1;
}

public static void main(String args[])
{

int arr[] = {10, 20, 40, 60, 5, 8}, n = 6;

int x = 5;

System.out.println(search(arr, n, x));      // OUTPUT : 4

}

}

// Naive Code

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

class GFG
{
static int search(int arr[], int n, int x)
{
for(int i = 0; i < n; i++)
if(arr[i] == x)
return i;

return -1;
}

public static void main(String args[])
{
int arr[] = {100, 200, 400, 1000, 10, 20}, n = 6;

int x = 10;

System.out.println(search(arr, n, x));      // OUTPUT : 4
}

}```
```// Efficient Code

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

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

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

if((mid == 0 || arr[mid - 1] <= arr[mid]) &&
(mid == n - 1 || arr[mid + 1] <= arr[mid]))
return mid;
if(mid > 0 && arr[mid - 1] >= arr[mid])
high = mid -1;
else
low = mid + 1;
}

return -1;
}

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

System.out.println(getPeak(arr, n));    //   OUTPUT : 20
}

}

// Naive Code

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

class GFG
{
static int getPeak(int arr[], int n)
{
if(n == 1)
return arr[0];
if(arr[0] >= arr[1])
return arr[0];
if(arr[n - 1] >= arr[n - 2])
return arr[n - 1];

for(int i = 1; i < n - 1; i++)
if(arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])
return arr[i];

return -1;
}

public static void main(String args[])
{
int arr[] = {5, 10, 11, 12, 20, 12}, n = 6;

System.out.println(getPeak(arr, n));  //   OUTPUT : 2
}

}```
```// Java implementation using Hashing
import java.io.*;
import java.util.HashSet;

class PairSum {

static void printpairs(int arr[], int sum)
{
HashSet<Integer> s = new HashSet<Integer>();
for (int i = 0; i < arr.length; ++i) {
int temp = sum - arr[i];

// checking for condition
if (s.contains(temp)) {
System.out.println("Pair with given sum " + sum + " is (" + arr[i] + ", " + temp + ")");
}
}
}

// Main to test the above function
public static void main(String[] args)
{
int A[] = { 1, 4, 45, 6, 10, 8 };
int n = 16;
printpairs(A, n);
}
}

// OUTPUT : Pair with given sum 16 is (10, 6)```
```import java.util.*;
import java.io.*;

class Solution
{
static int isPresent(int arr[], int n, int sum)
{
int l = 0, h = n-1;

while(l <= h)
{
if(arr[l] + arr[h] == sum)
return 1;
else if(arr[l] + arr[h] > sum)
h--;
else l++;
}

return 0;
}

public static void main (String[] args)
{
int arr[] = new int[]{2, 3, 7, 8, 11};
int n = arr.length;
int sum = 14;

System.out.println(isPresent(arr, n, sum));    // OUTPUT : 1
}
}```
```// Java program to find a triplet
class FindTriplet {

// returns true if there is triplet with sum equal
// to 'sum' present in A[]. Also, prints the triplet
boolean find3Numbers(int A[], int arr_size, int sum)
{
int l, r;

/* Sort the elements */
quickSort(A, 0, arr_size - 1);

/* Now fix the first element one by one and find the
other two elements */
for (int i = 0; i < arr_size - 2; i++) {

// To find the other two elements, start two index variables
// from two corners of the array and move them toward each
// other
l = i + 1; // index of the first element in the remaining elements
r = arr_size - 1; // index of the last element
while (l < r) {
if (A[i] + A[l] + A[r] == sum) {
System.out.print("Triplet is " + A[i] + ", " + A[l] + ", " + A[r]);
return true;
}
else if (A[i] + A[l] + A[r] < sum)
l++;

else // A[i] + A[l] + A[r] > sum
r--;
}
}

// If we reach here, then no triplet was found
return false;
}

int partition(int A[], int si, int ei)
{
int x = A[ei];
int i = (si - 1);
int j;

for (j = si; j <= ei - 1; j++) {
if (A[j] <= x) {
i++;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
int temp = A[i + 1];
A[i + 1] = A[ei];
A[ei] = temp;
return (i + 1);
}

/* Implementation of Quick Sort
A[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(int A[], int si, int ei)
{
int pi;

/* Partitioning index */
if (si < ei) {
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}

// Driver program to test above functions
public static void main(String[] args)
{
FindTriplet triplet = new FindTriplet();
int A[] = { 1, 4, 45, 6, 10, 8 };
int sum = 22;
int arr_size = A.length;

triplet.find3Numbers(A, arr_size, sum);    // OUTPUT : Triplet is 4, 8, 10
}
}
```
```import java.util.*;
import java.io.*;

class GFG
{
static double getMed(int a1[], int a2[], int n1, int n2)
{
int begin1 = 0, end1 = n1;

while(begin1 < end1)
{
int i1 = (begin1 + end1) / 2;
int i2 = ((n1 + n2 + 1) / 2 )- i1;

int min1 = (i1 == n1)?Integer.MAX_VALUE:a1[i1];
int max1 = (i1 == 0)?Integer.MIN_VALUE:a1[i1 - 1];

int min2 = (i2 == n2)?Integer.MAX_VALUE:a2[i2];
int max2 = (i2 == 0)?Integer.MIN_VALUE:a2[i2 - 1];

if(max1 <= min2 && max2 <= min1)
{
if((n1 + n2) % 2 == 0)
return ((double)Math.max(max1, max2) + Math.min(min1, min2)) / 2;
else
return (double) Math.max(max1, max2);
}
else if(max1 > min2)
end1 = i1 - 1;
else
begin1 = i1 + 1;
}

return -1;
}

public static void main(String args[])
{
int a1[] = {10, 20, 30, 40, 50}, n1 = 5, a2[] = {5, 15, 25, 35, 45}, n2 = 5;

System.out.println(getMed(a1, a2, n1, n2));     // OUTPUT : 27.5
}

}```
```// Method-2 : Time Complexity : O(n),  Auxiliary Space : O(1)

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

class GFG
{

static int repeat(int arr[], int n)
{
int slow = arr[0], fast = arr[0];

do{
slow = arr[slow];
fast = arr[arr[fast]];

}while(slow != fast);

slow = arr[0];

while(slow != fast)
{
slow = arr[slow];
fast = arr[fast];
}
return slow;
}

public static void main(String args[])
{
int arr[] = {1, 3, 2, 4, 6, 5, 7, 3}, n= 8;

System.out.println(repeat(arr, n));     // OUTPUT : 3
}

}

// Method-1 : Time Complexity : O(n),  Auxiliary Space : O(n)

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

class GFG
{
static int repeat(int arr[], int n)
{
boolean visit[] = new boolean[n];

for(int i = 0; i < n; i++)
{
if(visit[arr[i]])
return arr[i];
visit[arr[i]] = true;
}

return -1;
}

public static void main(String args[])
{
int arr[] = {0, 2, 1, 3, 2, 2}, n= 6;

System.out.println(repeat(arr, n));     // OUTPUT : 2
}

}```
```// Binary Search : Time Complexity : O(n * log(sum - mx))   or   O(n * log(sum))

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

class GFG {

public static void main(String args[])
{
int arr[]={10,20,10,30};
int n=arr.length;
int k=2;

System.out.print(minPages(arr,n,k));     // OUTPUT : 40
}

public static boolean isFeasible(int arr[],int n,int k, int ans){
int req=1,sum=0;
for(int i=0;i<n;i++){
if(sum+arr[i]>ans){
req++;
sum=arr[i];
}
else{
sum+=arr[i];
}
}
return (req<=k);
}

public static int minPages(int arr[],int n, int k){
int sum=0,mx=0;
for(int i=0;i<n;i++){
sum+=arr[i];
mx=Math.max(mx,arr[i]);
}
int low=mx,high=sum,res=0;

while(low<=high){
int mid=(low+high)/2;
if(isFeasible(arr,n,k,mid)){
res=mid;
high=mid-1;
}else{
low=mid+1;
}
}
return res;
}
}

// Naive Method : Time : Exponential (very slow)

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

class GFG {

public static void main(String args[])
{
int arr[]={10,20,10,30};
int n=arr.length;
int k=2;

System.out.print(minPages(arr,n,k));     // OUTPUT : 40
}

public static int sum(int arr[],int b, int e){
int s=0;
for(int i=b;i<=e;i++)
s+=arr[i];
return s;
}

public static int minPages(int arr[],int n, int k){
if(k==1)
return sum(arr,0,n-1);
if(n==1)
return arr[0];
int res=Integer.MAX_VALUE;
for(int i=1;i<n;i++){
res=Math.min(res,Math.max(minPages(arr,i,k-1),sum(arr,i,n-1)));
}
return res;
}
} ```