Binary Search Algorithm | Lecture-45 | Java and DSA Foundation course

In this video we will dive into the world of Binary Search in Java. We'll cover the basics of the algorithm, including its implementation in Java and the steps involved in the process. In addition, we'll also be solving important problems related to binary search. Whether you're a beginner or an experienced Java programmer, this video is perfect for anyone who wants to learn about binary search or improve their skills. So grab your notepad, sit back, and let's get started on our journey of understanding Binary Search in Java. Happy Learning. See you all in the lecture.

PW Skills is announcing the launch of the following programs,

Binary Batch:- Java-with-DSA-&-System-Design (Java with DSA & System Design)

Sigma Batch:- Full-Stack-Web-Development (MERN Stack)

Impact Batch:- Data-Science-Masters (Full Stack Data Science)

TIME STAMPS:
00:00 - Intro
00:54 - Today's checklist
01:35 - Binary Search Algorithm
04:46 - Binary Search Algorithm Example
15:15 - Binary Search Algorithm Code
21:31 - Recursive binary search
26:05 - Recursive binary search Code
29:50 - Recursive binary search analysis
37:24 - Time complexity analysis
48:01 - PROBLEM 01: Find the first occurence of a given element.
55:05 - PROBLEM 01: Find the first occurence of a given element. Code.
59:15 - PROBLEM 02: Find the square root.
01:11:56 - PROBLEM 02: Find the square root. Code
01:15:50 - Summary
01:16:21 - Follow up questions
01:16:54 - Next Lecture
01:17:05 - Outro

#Coding #Java #Tutorial #Binary #Search #BinarySearch #ProblemSolving #Problem #Solving #PWSkills #CollegeWallah #Solution #DSA #DataStructure #Algorithm

[CollegeWallahbyPW]

PW Skills is announcing the launch of the following programs,

Binary Batch:- Java-with-DSA-&-System-Design (Java with DSA & System Design)

Sigma Batch:- Full-Stack-Web-Development (MERN Stack)

Impact Batch:- Data-Science-Masters (Full Stack Data Science)

[hopeless]

We are enjoying the content of this awesome series ❤️❤️

[kartikpaul]

Thank you ma'am.I'm here from first day

[Abhishekyadav-kbni]

best lecture❤❤ on Binary search till date for sure...hatts off to u mam💥💥🛐🛐

[editingwithjatin]

1:15:56 Last Occurrence
public static int searchLastOccurrance(int[] arr, int size, int target) {
int st = 0, end = size - 1, ans = -1;
while (st <= end) {
int mid = st + (end - st) / 2; // find mid
if (target == arr[mid]) {
st = mid + 1; // It mean all the element are lesser. So, we have to search at the right side
ans = mid; // update ans to mid.
} else if (target < arr[mid]) {
end = mid - 1;
} else {
st = mid + 1;
}
}
return ans;
}

1:15:56
Sqrt with Precision
public static float findSqrtWithPricision(int num, intprecision) {
int st = 0, end = num;
double ans = -1.0;
while (st <= end) {
int mid = st + (end - st) / 2;
double val = mid * mid;
if (val == num) {
return mid;
} else if (val < num) {
st = mid + 1;
ans = mid;
} else {
end = end - 1;
}
}
double increment = 0.1;
for (int i = 0; i < precision; i++) {
while (ans * ans <= num) {
ans += increment;
}
ans = ans - increment;
increment = increment / 10;
}
return (float) ans;
}

[MayankGupta-qibp]

PROBLEM 1 FOLLOW UP QUESTION

public class problem_1 {
public static void last(int arr[], int t){
int st=0, end=arr.length-1;
int lo=-1;
while (st<=end){
int mid=st+(end-st)/2;
if (t==arr[mid]) {
lo=mid;
st=mid+1;
}
else if(t<arr[mid]) end=mid-1;
else st=mid+1;
}
System.out.println(lo);
}
public static void first(int arr[], int t){
int st=0, end=arr.length-1;
int fo=-1;
while (st<=end){
int mid=st+(end-st)/2;
if (t==arr[mid]) {
fo=mid;
end=mid-1;
}
else if(t<arr[mid]) end=mid-1;
else st=mid+1;
}
System.out.println(fo);
}
public static void main (String[] args){
int arr[]={1, 2, 5, 5, 5, 6, 6, 6, 8, 9, 9};
System.out.printf("First occurrence of %d is ", 6);
first(arr, 6);
System.out.printf("Last occurrence of %d is ", 6);
last(arr, 6);
}
}

[abhishekjha]

static int lastOcc(int[] arr, int target) {
int n = arr.length;
int st = 0, end = n - 1;
int mid = st + (end - st) / 2;
int fo = -1;
while (st <= end) {
mid = st + (end - st) / 2;
if (target == arr[mid]) {
fo = mid;
st = mid + 1;
} else if (target < arr[mid]) {
end = mid - 1;
} else {
st = mid + 1;
}
}

return fo;
}

[shankardeepak]

static int LastOccrance(int[] arr, int target) {
int start = 0, end = arr.length-1;
int fo = -1;
while(start<=end) {
int mid = start + (end-start)/2;
if(arr[mid]==target) {
fo = mid;
start = mid+1;
}else if(arr[mid] < target) {
start = mid+1;
}else {
end = mid-1;
}
}
return fo;

}

[khangaming]

code for last occurance : static int binarySearch(int[] arr, int target){

int left = 0;
int right = arr.length-1;
int startingIndex = -1;

while (left<=right){
int mid = left+(right-left)/2;
if (arr[mid] == target){//continue
startingIndex = mid;
left = mid+1;

}


else if (arr[mid]>target) {
right = mid-1;
}
else left=mid+1;
}

return startingIndex;

}

[prankcall]

package BinarySearch;

public class LastOccurance {

static int lastOccurence(int arr[], int tar)
{
int st = 0;
int end = arr.length-1;
int index = -1;
while (st <= end){
int mid = st+(end-st)/2;
if (tar == arr[mid]){
index = mid;
st= mid+1;
} else if (tar > arr[mid]) {
st = mid+1;
}
else
end = mid-1;
}
return index;
}
public static void main(String[] args) {
int arr[]= {5, 5, 5, 6, 6, 6, 7};
int tag = 5;
System.out.println("The last Occurrence of "+tag+ " is: " +lastOccurence(arr, tag) +" idx");
}
}

[deepakmodi]

// 1. Find the first occurence of a given element.
static int findFirstOccurence(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
int firstOccurence = -1;

while (start <= end) {
int mid = start + (end - start) / 2;

if (target == arr[mid]) {
firstOccurence = mid;
end = mid - 1;
}
else if (target > arr[mid]) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
return firstOccurence;
}

// 2. Find the last occurence of a given element.
static int findLastOccurence(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
int lastOccurence = -1;

while (start <= end) {
int mid = start + (end - start) / 2;

if (target == arr[mid]) {
lastOccurence = mid;
start = mid + 1;
}
else if (target > arr[mid]) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
return lastOccurence;
}

[aayushkamble]

By Recursion
public class LastOccurrence {
static int binarySearch(int []arr, int target, int start, int end, int ans){

if (start>end){
return ans;
}
int mid = start + (end-start)/2;
if (arr[mid]==target){
ans=mid;
return binarySearch(arr, target, mid+1, end, ans);
} else if (arr[mid]<target) {
return binarySearch(arr, target, mid+1, end, ans);
}else {
return binarySearch(arr, target, start, mid-1, ans);
}

}
public static void main(String[] args) {
int []array ={3, 4, 5, 5, 5, 6, 6, 7, 7, 9};
int ans=-1;
int target = 5;
System.out.println(binarySearch(array, target, 0, array.length-1, ans));
}
}

[hrithikrudra]

public static int lastOccurance(int arr[], int key){
int start=0;
int end=arr.length-1;
int fo=-1;
while(start<=end){
int mid=start+(end-start)/2;
if(arr[mid]==key){
fo=mid;
start=mid+1;
}
else if(arr[mid]>key){
end=mid-1;
}
else{
start=mid+1;
}

}
return fo;

}

[maxnigaming]

package Binary_Search;

public class FindSquareRootPrecision {
static int sqrt(int x){
int strt = 0;
int end = x;
int ans = -1;

while(strt<=end){
int mid = strt + ( end-strt)/2;
int val = mid*mid;
if (val==x){
return mid;

}else if (val < x){

strt = mid+1;
}else {
end =mid-1;
ans = mid;
}
}
return ans;
}
public static void main(String[] args) {
int x = 5;
System.out.println(sqrt(x));
}
}

[AyushSingh-hcpj]

Last Occurence
public class LastOccurence {
static int lastoccurence(int arr[], int x){
int st = 0;
int end = arr.length-1;
int lo = -1;
while(st <= end){
int mid = st + (end - st)/2;
if(arr[mid] == x){
lo = mid;
st = mid + 1;
} else if (x < arr[mid]) {
end = mid - 1;
}
else st = mid + 1;
}
return lo;
}
public static void main(String[] args) {
int arr[] = {1, 2, 3, 3, 4, 4, 15, 15, 15, 66, 66, 77};
int x = 15;

System.out.println(lastoccurence(arr, x));
}
}

[cs-rohitsahu]

Index of last occurance of an element of array is

import java.util.Scanner;

public class BinarySearchOccuranceIndex {
static int searchOccurance(int arr[], int target){
int n=arr.length;
int st=0;
int end=n-1;
int fo=-1;
while(st<=end){
int mid=st+(end-st)/2;
if(arr[mid]==target) {
fo = mid;
st=mid+1;
}
else if(target<arr[mid]){
end=mid-1;

}
else st=mid+1;

}
return fo;


}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int arr[]={2, 3, 4, 5, 5, 6};
System.out.println("enter no. you want to find fist occurance of ");
int target =sc.nextInt();

System.out.println("first occurance of "+target+" is "+searchOccurance(arr, target));


}
}

[akxxhil]

static int lastoccur(int arr[], int target){
int start=0;
int end=arr.length-1;
int lastoccur=-1;
while(start<=end){
int mid=start+(end-start)/2;
if (arr[mid]==target){
lastoccur=mid;
start=mid+1;

}
else if (arr[mid]<target){
start=mid+1;
}
else {
end=mid-1;
}

}
return lastoccur;

}
public static void main (String[] args){
int a[]={2, 5, 5, 5, 6, 6, 8, 9, 9, 9};
int target=5;
System.out.println(lastoccur(a, target));

}
} question : - last occurance

[ShivamTiwari-jj]

class HelloWorld {
public static int lastoccurence(int arr[], int t){
int st =0;
int end = arr.length;
int lo =-1;
while(st<=end){
int mid =st+(end-st)/2;
if(t==arr[mid]){
lo =mid;
st = mid+1;
}
else if(t>arr[mid]){
st =mid+1;
}
else {
end =mid-1;
}
}
return lo;
}
public static void main(String[] args) {
int arr[]={1, 2, 3, 4, 5, 5, 5, 6};
System.out.println(lastoccurence(arr, 5));
}
}

[codebyprince]

class Main {
static int LastOcc(int [] a, int x) {

int n = a.length;
int st = 0, end = n-1;
int fo = -1;

while (st <= end) {
int mid = st + (end-st)/2;

if (x == a[mid]) {
fo = mid;
st = mid+1;
}

else if (x < a[mid]) {
end = mid-1;
}
else {
st = mid+1;
}
}

return fo;




}
public static void main (String[] args) {
int [] a = {2, 2, 3, 3, 3, 4, 5, 5, 5};
int x = 5;
System.out.println(LastOcc(a, x));
}
}

Code -
Find Last occurrence in Java !

[somyalsinha]

In the main function, shouldn't the arr a be sorted because in binary search the array needs to be sorted??