top of page

Keep Reading !

You can also checkout more topics like...

peep-101_edited.png
EXPLORE COURSES (6).png
EXPLORE COURSES (9).png
EXPLORE COURSES (7)_edited.jpg

Binary Search


Problem : You are given a sorted array of size 'N' you have to find K from the array in O(log n ) time complexity. Input Format:

First line get input for 'N' (Where N is size of array)

Second line N space separated integers Third line K (Key value) Time Complexity:

O(Logn)


Example Input 01:
N = 5
arr[] = {0 1 2 4 6} 
K = 4
Example Output: 3
Explanation: 4 at index 3.

Example Input 02:
N = 5
arr[] = {0 1 2 4 6} 
K = 4
Example Output: Find at index 3
Explanation: 4 at index 3.

Example Input:
N = 5
arr[] = {10 11 12 24 36} 
K = 11
Example Output: Find at index 1
Explanation: 11 at index 1.


 

Solutions !


First of all the word Binary means 0 and 1 , so in easy way we can say there is two situation , situation 1 and situation 0 like wise here we divided the array by two, left subarray and right subarray, since the array is already sorted so we do not need to worry about the order of element so the main algo is first devide my current array find the middle element( if array is even then we either choose n/2+1 th element or n/2 only e.g. 6/2 = 3 or 4th element ) if we find the middle element the key element we need to retuen that index or we check that if the middle element greater than key element then we need to consider the left array or have to choose the right array, check till start position smaller than end.


For Better Explanation prefer this VIDEO

int binarysearch(int arr[], int n, int k) 
 {
     int start = 0;
     int end = n-1;
     while(start <= end)
   {
      int mid = (start + end)/2;
      if(arr[mid] == k){
         return mid;
           }
      if(arr[mid] > k)
      {
         end = mid-1;
         }else{
               start = mid+1;
               }
          }
       return -1;
   }


Click on the Execute button below for code up and running

If you have any further doubt then Comment down below.



Do You Know the Answer !

Binary Search applicable only

  • Sorted Array

  • Any array


156 views0 comments

Recent Posts

See All
bottom of page