Doubt after watching the lower bound and upper bound video

#1

Here none of the element is repeating itself so it is easy to apply the loop and the if conditions but will happen if element is repeating itself.
I watched the lower bound and upper bound video and got confused because there after finding the first occurence of the item we are not eliminating the part of the array and we are seaching the element both ways. I’m not able to explain my doubt but if somebody is able to get it, do explain it to me

#2

@rg361 I take it that problem you’re facing is: There is no problem if Elements are unique but there will be a problem if there are duplicate elements.So considering upper bound if we found the element we are searching we will cut left half of our array and will continue to search that element in remaining part and to execute this some changes are required in the binary search code : below is the code look for comments explanation.

import java.util.Arrays;
import java.util.Scanner;

public class HigherBoundIndexOfAData {

	public static void main(String{} args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int{} ar = new int{n};
		for(int i = 0; i < n; i++) {
			ar{i} = sc.nextInt();
		}
		Arrays.sort(ar);
		int x = sc.nextInt();
		int lo = 0;
		int hi = n-1;
		int mid = (lo+hi)/2;
//higher bound index store
		int hbi = -1;
		while(lo <= hi) {
			if(ar{mid} > x) {
				hi = mid-1;
			}
			else if(ar{mid} < x){
				lo = mid+1;
			}
			else {
//Note here we not breaking the loop when we found the element instead we are making lo = mid+1 bcoz higher bound if present will be there and eventually we will end up at higher bound.TRY DRY run for this code and you will learn why.
				hbi = mid;
				lo = mid+1;
			}
			mid = (lo+hi)/2;
		}
		System.out.println(hbe);
		sc.close();

	}

}

Now considering Lower bound whenever we found our element we will cut our right array and will continue binary search on the left part.look for comment explaination.

import java.util.Arrays;
import java.util.Scanner;

public class LowerBoundIndexOfAData {

	public static void main(String{} args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int{} ar = new int{n};
		for(int i = 0; i < n; i++) {
			ar{i} = sc.nextInt();
		}
		Arrays.sort(ar);
		int x = sc.nextInt();
		int lo = 0;
		int hi = n-1;
		int mid = (lo+hi)/2;
//higher bound index store
		int lbi = -1;
		while(lo <= hi) {
			if(ar{mid} > x) {
				hi = mid-1;
			}
			else if(ar{mid} < x){
				lo = mid+1;
			}
			else {

//Note here we not breaking the loop when we found the element instead we are making hi = mid-1 bcoz lower bound if present will be there and eventually we will end up at lower bound.TRY DRY run for this code and you will learn why.
				lbi = mid;
				hi = mid-1;
			}
			mid = (lo+hi)/2;
		}
		System.out.println(lbe);
		sc.close();
	}

}
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.