Tag Archives: Binary Search

Find First and Last Position of Element in Sorted Array

By | | , ,
Leave a comment

Find first and last position of element in sorted array.

Given a sorted array which contains duplicate elements. Write a code to find first and last position of a number in a sorted array.

OR

Find first and last occurrences of x in sorted array where x is a target value.

If a number is not found return -1.

For example –

Example 1 –

Input : {1, 4, 7, 8, 8, 11, 11, 11, 11, 12, 13, 13} , target = 11

Output: {5, 8}

The first index of 11 is 5 and last index is 8.

Example 2 –

Input: {1, 6, 7, 7, 8, 8, 9, 9},  target = 5

    Output: {-1, -1}

    The target value is not found.

NOTE – We have to solve this problem in O(logn) time complexity.

→

Binary Search using Recursion in Java

By | | , ,
3 Comments

In this tutorial, I am going to discuss the implementation of a Binary search using recursion in java.

Given an array of sorted integers and a number k. We have to write a code to search  an element k in an array.

For example:

Input: {2, 3, 4, 5, 7, 8},     k = 5

Output: 3 (5 is found at 3rd index)

Input array is sorted and we have to find 5 in this array. The element is found at index 3.

→