How Binary Search Works with Example

How Binary Search Works with Example


Binary Search : 

To find an value in array we are having different ways and binary search is one of the most efficient way. It will reduce the no. of iteration to find the solution thus get us the solution quickly.

In simple form, we need to do 3 checks as follows : 

target value = the value to find in the array.

    1. if the target value = array[mid] => return the index.

    2. if target value is smaller, than start searching on the left side else search on right side.

    3. Keep repeating the process till either you get the value or till you iterate elements in array.


How Binary Search Works : 

Learn by solving a Problem : 

Write a method to find an index of an element in an ascending Sorted Array using Binary Search. 

If element doesn't exist return -1.

Illustration 1 :    a[] = {1,2,4,5,7,8,10} , Find 5 

                            Output =>  3  

                            Explanation : Index of 5 is 3.

Illustration 2 :    a[] = {1,2,4,5,7,8,10} , Find 6 

                            Output =>  -1.

                            Explanation :  As 6 is not available in array.

Solution :
                                 public int BinarySearch(int[] arr, int target) 
    {
        //int a = -1;
        
        // First Approach - Using IndexOf
        //a = Array.IndexOf(arr,target);
        
        //Second Approach -- Linear Search         
        //for(int index =0 ; index < arr.Length; index++)
        //{
        //    if(arr[index] == target)
        //    {
        //        a = index;
        //        break;
        //    }
        //}
        
        // Third Approach - Binary Search
        int arrayLength = arr.Length;
                
        if(arrayLength == 1)
        {
            if(arr[0] == target)
                return 0;
            else
                return -1;
        }
        else
        {
            int center, first = 0, last = arrayLength - 1;
            while (first < last || first == last)
            {
                center = first + ((last - first) / 2);  // Check the Link 1
                if(arr[center] == target)
                    return center;        
                if(arr[center] < target)
                    first = center + 1;
                else
                    last = center - 1;                
            }            
        }        
        return -1;                
    }

Input :    arr [] = {-1,0,3,5,9,12,15,19,21,25,27,29,30}; target = 17

Output : -1

Step 1 : Initializing values

          center, firstIndex = 0, lastIndex = 12

Step 2 : Find center value and check arr[center] with Target value

 firstIndex : 0 lastIndex : 12

 center : 6 target :17

 center : 6 , arr[center] : 15 target :17

Step 3: As  arr[center] > target  => firstIndex = center + 1

 firstIndex : 7 lastIndex : 12

 center : 9 target :17

 center : 9 , arr[center] : 25 target :17

Step 3: As  arr[center] <  target  => lastIndex = center  - 1

 firstIndex : 7 lastIndex : 8

 center : 7 target :17

 center : 7 , arr[center] : 19 target :17

Step 4 : It came out of loop. 

Link 1 : Explanation why we put (firstIndex + (lastIndex - firstIndex)/2) as value


#HappyLearning

Location: Haribhau Upadhyay Nagar, Ajmer, Rajasthan 305004, India

Comments

Post a Comment

Popular posts from this blog

Border Radius not working in Outlook Email template

Hi techies, We can have the different ways to search it on google or stack overflow that border radius not working in outlook CSS , how to make image as round or roundrect, oval, circle in outlook,  how to put border radius to image  in outlook email template,  etc. I assure you that at the end of this tech blog you can able to find all the answers related to the Outlook email template and its CSS behavior. Lets get started... Just a little brief that why the border radius is not working in the outlook email template Outlook still support the Vector markup language (VML)  when it comes to support the email template CSS which doesn't support most of the CSS3 or HTML5 features that most of the web browsers do. As Border-radius is a feature of CSS3 so its not is not supported by Microsoft outlook. It means to meet your requirement you have to take reference from VML. Actually, I made it easier for you. Below is the code snippet that will work to solve the problem. Code ...
Read more

C# .Net Core Interview Questions for Freshers and Experienced Developers

  C#, .NetFramework, .Net Core interview Questions For Angular and SQL Interview Questions, click here...! 1. IOC (Inversion of Control) Container in .NET Core The IOC container in .NET Core is responsible for managing object creation and their dependencies. It's used for Dependency Injection (DI), making it easy to manage lifecycles (transient, scoped, singleton). Example of registering a service: public void ConfigureServices(IServiceCollection services) {     services.AddScoped<IMyService, MyService>();  // DI registration } 2. Configure and ConfigureServices - When to Use What ConfigureServices: Used to register services with the dependency injection container. Typically includes services like database context, authentication, and MVC. Configure: Used to define the middleware pipeline (how requests are processed). Example: public void ConfigureServices(IServiceCollection services) {     services.AddControllers();     services.AddDbContex...
Read more

15 ways to keep your team motivated while working remotely ?

Image
Remote teams is a new trend after the Coronavirus pandemic and it changed how the world sees the Work from Home option. Its not only safe but also a cost effective measure which most of the companies are taking. Thus, many companies like salesforce and twitter has already made it as a company policy and option to go office for work. Handling a team is not everyone's cup of tea. It is even more tougher while a team is working remotely. So, here are few ways that make it easy for you to connect with your team efficiently and help you to have a engaged and motivated team.  15 ways to motivate your team while working remotely -  1. Practice Emotional Intelligence 2. Empathize with people 3. Remember the old time which you spent in office and rejoice those moments. 4. Talk about things other than office work. 5. Appreciate people and show gratitude. 6. Help them to solve their problems. 7. Motivate them to do things which they like other than office work 8. Be with them if they nee...
Read more