Kavyabala
Day 13 of Landing a Job in 30 days

Day 13 of Landing a Job in 30 days

Kavyabala's photo
Kavyabala
·

2 min read

Hi guys✋,This is day 13 of landing a Job in 30days👩‍💻.

Today we will learn about binary search.

Binary Search

Before getting into things we need to know why we need binary search?

Binary search is known for being an O(log n) which means that the time complexity of our operation is proportional to the logarithm of its input size.

Now just imagine that we wanted to search an element inside a list of one million elements, we would still be able to run the operation pretty fast and efficient. We always need to consider the worst-case in these scenarios, and to search for a specific element inside a sorted list of elements, binary search is ideal for that.

Lets Understand the concept in it.

When an array is sorted then without any second thought you can use binary search.

In the above example the we have to find the target element 27.There are three condition for that

  • If arr[mid] ==target then return arr[mid]

  • else if arr[mid]>target then end=mid-1

  • start=mid+1

      class BinarySearch{
        public static void main(Strings args[]){
          int arr={1,5,8,10,13,16,27,32,45,60}
          int target =27;
          int start =0;
          int end= arr.length-1;
          while(start<=end){
           int mid = start+(end-start)/2;
           if(arr[mid]==target)
                  System.out.println(mid);
           else if(arr[mid]>target)
                  end=mid-1;
           else 
                  start=mid+1;
           }

       }
  }

To understand the working visually copy the code and paste it in this website

https://pythontutor.com/java.html#mode=edit

So Time complexity and space complexity of Binary search is

Tomorrow we will see about Lower and upper bound.

Problem solved today

Happy Coding!!!!😃

Resources

https://youtu.be/f6UU7V3szVw?feature=shared

https://www.youtube.com/playlist?list=PLgUwDviBIf0pMFMWuuvDNMAkoQFi-h0ZF

30daysofcode