Snippets Collections
#include <stdio.h>  
int binarySearch(int a[], int beg, int end, int val)    
{    
    int mid;    
    if(end >= beg)     
    {        mid = (beg + end)/2;    
/* if the item to be searched is present at middle */  
        if(a[mid] == val)    
        {                 
            return mid+1;    
        }    
            /* if the item to be searched is smaller than middle, then it can only be in left subarray */  
        else if(a[mid] < val)     
        {  
            return binarySearch(a, mid+1, end, val);    
        }    
            /* if the item to be searched is greater than middle, then it can only be in right subarray */  
        else     
        {  
            return binarySearch(a, beg, mid-1, val);    
        }          
    }    
    return -1;     
}   
int main() {  
  int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // given array  
  int val = 40; // value to be searched  
  int n = sizeof(a) / sizeof(a[0]); // size of array  
  int res = binarySearch(a, 0, n-1, val); // Store result  
  printf("The elements of the array are - ");  
  for (int i = 0; i < n; i++)  
  printf("%d ", a[i]);   
  printf("\nElement to be searched is - %d", val);  
  if (res == -1)  
  printf("\nElement is not present in the array");  
  else  
  printf("\nElement is present at %d position of array", res);  
  return 0;  
}  
// Iterative Solution : Time Complexity : O(LogN),  Aux. Space : O(1)

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int bSearch(int arr[], int n, int x)
	{
		int low = 0, high = n - 1;

		while(low <= high)
		{
			int mid = (low + high) / 2;

			if(arr[mid] == x)
				return mid;

			else if(arr[mid] > x)
				high = mid - 1;

			else
				low = mid + 1;
		}

		return -1;
	}

	public static void main(String args[]) 
	{
        int arr[] = {10, 20, 30, 40, 50, 60}, n = 6;

		int x = 25;
    
        System.out.println(bSearch(arr, n, x));  // Output : -1
		
    } 

}





// Recursive Solution : Time Complexity : O(LogN),  Aux. Space : O(logN)

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int bSearch(int arr[], int low, int high, int x)
	{
		if(low > high)
			return -1;

		int mid = (low + high) / 2;

		if(arr[mid] == x)
			return mid;

		else if(arr[mid] > x)
			return bSearch(arr, low, mid - 1, x);

		else
			return bSearch(arr, mid + 1, high, x);
	}

	public static void main(String args[]) 
	{
        int arr[] = {10, 20, 30, 40, 50, 60, 70}, n = 7;

		int x = 20;

        System.out.println(bSearch(arr, 0, n - 1, x));  // Output : 1
    } 
}
int firstOccurance(vector<int> &ar,int target){
  int low = 0,high = ar.size()-1,ans = -1;
  while(low<=high){
    int mid = low+(high-low)/2;
    
    if(ar[mid]==target){
      //mid can be our answer but we are not sure so reduce the search space
      ans = mid;
      high = mid-1;//for first occurance go to left
    }
    else if(ar[mid]>target)
      high = mid-1;
    else
      low = mid+1;
  }
  return ans;//if element is not present ans will remain -1,and will be returned as it is.
}

int lastOccurance(vector<int> &ar,int target){
  
  int low = 0,high = ar.size()-1,ans = -1;
  while(low<=high){
    int mid = low+(high-low)/2;
    
    if(ar[mid]==target){
      //mid can be our answer but we are not sure so reduce the search space
      ans = mid;
      low = mid+1; //for lasat occurance go to right
    }
    else if(ar[mid]>target)
      high = mid-1;
    else
      low = mid+1; 
  }
  
  return ans;//if element is not present ans will remain -1,and will be returned as it is.
}
//whenever there is sorted array first think of binary search

int binarySearch(vector<int> &ar, int target)
{

    int low = 0, high = ar.size() - 1;

    while (low <= high)
    {
        int mid = low + (high - low) / 2;

        if (ar[mid] == target)
            return mid;
        else if (ar[mid] > target)
            high = mid - 1; // go to left
        else
            low = mid + 1; // go to right
    }

    return -1; // if element is not found
}

//the above solution is only ,if array is sorted in ascending order
//for descending sorted array condition's to go to left and right reverse

//time complexity :- O(logn);
star

Thu May 26 2022 15:44:58 GMT+0000 (UTC)

#c #binarysearch
star

Sun Jan 16 2022 07:18:37 GMT+0000 (UTC)

#binarysearch
star

Sun Jan 16 2022 06:59:21 GMT+0000 (UTC)

#binarysearch

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension