Transition Point

Last Updated on April 14, 2022 by Ria Pathak

CONCEPTS USED:

Binary Search

DIFFICULTY LEVEL:

Easy

PROBLEM STATEMENT(SIMPLIFIED):

Given a sorted array of 0's and 1's of size N, find the first occurrence of 1 if present else return -1.

See original problem statement here

For Example:

Input : arr = [0, 0, 0, 1, 1]

Output : 3

Explanation : First occurrence of 1 is present at 3rd index.

Can we use Binary Search here ?

Given that the array is sorted, Binary Search would be an efficient alternative to quickly search for the first occurrence of 1 in Logarithmic Time Complexity.

SOLVING APPROACH:

1. The idea is to use Binary Search.

2. Initialize mid = start + (end - start) / 2 and flag =-1, where start is the starting index of the array and end is the last index.

3. Check if 1 is present at mid index, if Yes save this index in flag and search for a smaller index by searching in the left sub array by marking, end = mid -1.

4. Else keep on searching in the right half by marking
   start = mid + 1.

5. Keep doing it till start becomes less than equal to end, finally return flag.

ALGORITHM:

flag = -1

while (start <= end)
  mid = start + (end - start) / 2

  if (element at mid index = 1)
    flag = mid
    end = mid - 1

  else
    start = mid + 1

return flag

SOLUTIONS:

#include <stdio.h>

int firstOccurence(int *arr, int start, int end, int flag){
  while(start <= end){
    int mid = start + (end - start) / 2;
      if(arr[mid] == 1){
        flag = mid;
        end = mid - 1;
      }
      else{
        start = mid + 1;
      }
  }
  return flag;
}

int main()
{
  int t; scanf("%d", &t);
  while(t--){
    int n; scanf("%d", &n);
    int arr[n];
    for(int i = 0; i<n; i++)
      scanf("%d", &arr[i]);
    printf("%d\n", firstOccurence(arr, 0, n-1,-1));
  }

  return 0;
}

#include <bits/stdc++.h>
using namespace std;

int firstOccurence(int *arr, int start, int end, int flag = -1){
  while(start <= end){
    int mid = start + (end - start) / 2;
      if(arr[mid] == 1){
        flag = mid;
        end = mid - 1;
      }
      else{
        start = mid + 1;
      }
  }
  return flag;
}

int main()
{
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    int arr[n];
    for(int i = 0; i<n; i++)
      cin>>arr[i];
    cout<<firstOccurence(arr, 0, n-1)<<"\n";
  }

  return 0;
}

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

public class Main {
  static int firstOccurence(int[] arr, int start, int end, int flag){
    while(start <= end){
      int mid = start + (end - start) / 2;
        if(arr[mid] == 1){
          flag = mid;
          end = mid - 1;
        }
        else{
          start = mid + 1;
        }
    }
    return flag;
}
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t != 0){
      int n = sc.nextInt();
      int arr[] = new int[n];
      for(int i = 0; i<n; i++)
        arr[i] = sc.nextInt();
      System.out.println(firstOccurence(arr, 0, n-1, -1));
      t--;
    }
  }
}

This article tried to discuss Binary Search. Hope this blog helps you understand the concept. To practice more problems you can check out MYCODE | Competitive Programming.