Binary Search

Binary search is the most prominent example of a Divide and Conquer algorithm.
Suppose you are given an array of size in sorted order and you have to return the index of an element.

Basic algorithm is

initialize low = 0, high = N, mid = (low + high)/2
check if element is at position mid; if found, return  
else depending upon value of mid is lower or greater, we explore the right side of the array or the left side

Sample recursive function code in C++:

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin)
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);

      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        return binary_search(A, key, imin, imid - 1);
      else if (A[imid] < key)
        // key is in upper subset
        return binary_search(A, key, imid + 1, imax);
      else
        // key has been found
        return imid;
    }
}

Sample iterative solution in C++:

int binary_search(int A[],int N,int key){

    // considering 1 based index
    int low , high , mid ;
    low = 1 ;
    high = N ;
    while(low <= high){
        mid = (low + high)/2 ;
        if(A[mid] == key){
            return mid ; // a match is found
        }else if(A[mid] < key){ // if middle element is less than the key 
            low = mid + 1 ;     // key will be right part if it exists
        }else{
            high = mid - 1 ;    // otherwise key will be in left part if it exists
        }
    }
    return -1 ; // indicating no such key exists 
}

Common Variations of BinarySearch:

  1. LowerBound: find an element in a sorted array of intergers such that , where key is given.
  2. UpperBound: find an element in a sorted array of intergers such that , where key is given.

UpperBound Implementation in C++:

int UpperBound(int A[],int N,int K){
    int low , high , mid ;
    low = 1 ;
    high = N ;
    while(low <= high){
        mid = ( low + high ) / 2 ; // finding middle element 
        if(A[mid] > K && ( mid == 1 || A[mid-1] <= K )) // checking conditions for upperbound
            return mid ;
        else if(A[mid] > K) // answer should be in left part 
            high = mid - 1 ;
        else                // answer should in right part if it exists
            low = mid + 1 ;
    }
    return mid ; // this will execute when there is no element in the given array which > K
}

LowerBound Implementation in C++:

int LowerBound(int A[],int N,int K){
    int low , high , mid ;
    low = 1 ;
    high = N ;
    while(low <= high){
        mid = ( low + high ) / 2 ; // finding middle element 
        if(A[mid] >= K && ( mid == 1 || A[mid-1] < K )) // checking conditions for lowerbound
            return mid ;
        else if(A[mid] >= K) // answer should be in left part 
            high = mid - 1 ;
        else                // answer should in right part if it exists
            low = mid + 1 ;
    }
    return mid ; // this will execute when there is no element in the given array which >= K
}

NOTE : C++ STL (Standard Template Library) already contains implementation of all of these functions. Check out here for additional knowledge binarysearch, lowerbound, upperbound

 
Related challenge for Binary Search
Go to Top

Greedy Technique

A greedy algorithm is an algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

A very common problem which gives good insight into this is the Job Scheduling Problem.

You have jobs numbered and you have the start times and the end times for the job. Which jobs should you choose such that you get the maximal set of non-overlapping jobs?

The correct solution to this problem is to sort all the jobs on the basis of their end times and then keep on selecting the job with the minimal index in this list which does not overlap with currently selected jobs.

Sounds intuitive, but why does it work?

Well, since each job has equal weight, selecting the one which makes way for newer jobs sooner is optimal. Although a more formal argument can be made for a rigorous proof, the intuition behind it is similar.

Now, let's consider another problem. You again have jobs. Each job can be completed at any time and takes time to complete and has a point value of . But with each second, the point value of the job decreases by . If you have to complete all the jobs, what is the maximum points that you can get?

The problem basically asks us for an order of accomplishing the jobs.

Here, doing the job with higher first makes sense. At the same time, doing the job with lower also sounds good. So how do we decide?

Assume you have just jobs which, without loss of generality, can be numbered as and .

Now, if you do job before job , your net score is:


Otherwise,

If then:
In other words, it is optimal to do job before job iff .

Notice that this argument can be applied to jobs as a sorting rule. The job with maximum value should be done first and so on.

This gives us the optimal ordering and is also in line with our intuition.

Greedy doesn't always work

Greedy solutions are usually good whenever they exist, because they are usually easy to implement and usually have a fast running time. However, greedy algorithms don't always work! By this, we don't mean that the greedy algorithm fails to return the correct answer on all inputs. Instead, we mean that the algorithm fails on at least one input.

For example, consider the following problem: You again have jobs, and the job takes time to complete and has a point value of . This time, the point values do not decrease over time, and you don't have to finish all jobs. Unfortunately you only have a total of time to spend. What is the maximum points you can get?

One greedy algorithm that comes to mind is the following: while there is still time remaining, take the job with the largest point value that can be finished within the remaining time. Intuitively, this can be seen to work in some cases. However, this fails in the following set of jobs:

Assuming , the greedy algorithm mentioned above first takes job , then job , for a total of points. However, this is not the global optimum, because you can take jobs and for a total of points, which is much higher.

The next greedy algorithm we can try is to always take the job which takes the shortest amount of time to finish. However, this also fails the set of jobs above (where you only get points).

You can probably try crafting a more sophisticated greedy algorithm than the ones we described, but it probably won't work, i.e. it will probably fail on some input. This is because the problem we described to you is equivalent to the knapsack problem which currently has no known efficient algorithm!

 
Related challenge for Greedy Technique
Go to Top
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score