DEV Community: Mostafa Shariare

Building a Rotated Sorted Array Search in Java: Understanding Pivot and Binary Search

Mostafa Shariare — Fri, 27 Sep 2024 12:25:43 +0000

What is a Rotated Sorted Array?

Consider a sorted array, for example:

[1, 2, 3, 4, 5, 6]

Now, if this array is rotated at some pivot, say at index 3, it would become:

[4, 5, 6, 1, 2, 3]

Notice that the array is still sorted, but it is divided into two parts. Our goal is to search for a target value in such arrays efficiently.

The Search Strategy

To search in a rotated sorted array, we need to:

Find the Pivot: The pivot is the point where the array transitions from larger to smaller values.
Binary Search: Once we find the pivot, we can use binary search on the appropriate half of the array.

Step-by-Step Code Explanation

class Solution {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 1, 2, 3}; // Example of rotated sorted array
        int target = 5;

        // Searching for the target
        int result = search(arr, target);

        // Displaying the result
        System.out.println("Index of target: " + result);
    }

    // Main search function to find the target in a rotated sorted array
    public static int search(int[] nums, int target) {
        // Step 1: Find the pivot
        int pivot = searchPivot(nums);

        // Step 2: If no pivot, perform regular binary search
        if (pivot == -1) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }

        // Step 3: If the target is at the pivot, return the pivot index
        if (nums[pivot] == target) {
            return pivot;
        }

        // Step 4: Decide which half of the array to search
        if (target >= nums[0]) {
            return binarySearch(nums, target, 0, pivot - 1); // Search left side
        } else {
            return binarySearch(nums, target, pivot + 1, nums.length - 1); // Search right side
        }
    }

    // Binary search helper function
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (arr[mid] == target) {
                return mid; // Target found
            } else if (target < arr[mid]) {
                end = mid - 1; // Search left half
            } else {
                start = mid + 1; // Search right half
            }
        }
        return -1; // Target not found
    }

    // Function to find the pivot index in a rotated sorted array
    static int searchPivot(int[] arr) {
        int start = 0;
        int end = arr.length - 1;

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

            // Check if mid is the pivot point
            if (mid < end && arr[mid] > arr[mid + 1]) {
                return mid;
            }

            // Check if the pivot is before the mid
            if (mid > start && arr[mid] < arr[mid - 1]) {
                return mid - 1;
            }

            // Decide whether to move left or right
            if (arr[mid] <= arr[start]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return -1; // No pivot found (array is not rotated)
    }
}

Explanation of the Code

search():
- This function is responsible for searching for the target in the rotated sorted array.
- First, we find the pivot using the searchPivot() function.
- Depending on the pivot's position, we then decide which half of the array to search using binary search.
binarySearch():
- A standard binary search algorithm to find the target in a sorted sub-array.
- We define the start and end indices and progressively narrow the search space.
searchPivot():
- This function identifies the pivot point (the place where the array rotates).
- The pivot is the index where the sorted order is "broken" (i.e., the array goes from a higher value to a lower value).
- If no pivot is found, it means the array was not rotated, and we can perform a regular binary search.

How the Algorithm Works

For an array like [4, 5, 6, 1, 2, 3]:

The pivot is at index 2 (6 is the largest, and it is followed by 1, the smallest).
We use this pivot to divide the array into two parts: [4, 5, 6] and [1, 2, 3].
If the target is greater than or equal to the first element (4 in this case), we search the left half. Otherwise, we search the right half.

This method ensures that we search efficiently, achieving a time complexity of O(log n), similar to a standard binary search.

Conclusion

Rotated sorted arrays are a common interview question and a useful challenge to deepen your understanding of binary search. By finding the pivot and adapting our binary search accordingly, we can efficiently search through the array in logarithmic time.

If you found this article helpful, feel free to connect with me on LinkedIn or share your thoughts in the comments! Happy coding!

🚀 Solving LeetCode 852: Peak Index in a Mountain Array Using Binary Search

Mostafa Shariare — Thu, 19 Sep 2024 16:49:54 +0000

📝 Problem Statement:

Given a mountain array, find the peak index. A mountain array is one where:

The elements first strictly increase, reaching a peak.
After the peak, they strictly decrease.

You're tasked with finding the index of that peak element.

Example:

Input: arr = [0, 2, 3, 4, 5, 3, 1]
Output: 4

Here, arr[4] = 5 is the peak element.

🛠️ Approach:

A brute force approach would involve iterating through the array to find the peak by checking when an element is greater than its neighbors. But we can do better.

Since the array is structured like a mountain, with an increasing part followed by a decreasing part, we can leverage binary search to efficiently solve this problem.

The idea is:

Use binary search to find the peak.
If the middle element is greater than the next one (arr[mid] > arr[mid + 1]), this means we're on the descending part of the mountain, so the peak is to the left, including mid.
Otherwise, the peak is to the right, excluding mid.

This approach runs in O(log n) time, making it much faster than a linear search.

🔨 Solution Code:

Here's the code to solve the problem using binary search:

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int start = 0;
        int end = arr.length - 1;

        // Binary Search loop
        while (start < end) {
            int mid = start + (end - start) / 2;

            // If mid is greater than the next element, peak is on the left
            if (arr[mid] > arr[mid + 1]) {
                end = mid;
            } else {
                // If mid is less than the next element, peak is on the right
                start = mid + 1;
            }
        }
        // Start and end will converge to the peak index
        return start;
    }
}

🔍 Explanation:

Initial Setup:
- We define start as 0 and end as the last index of the array.
Binary Search:
- The loop continues until start is equal to end.
- We calculate mid as the average of start and end.
- If the middle element is greater than the next one (arr[mid] > arr[mid + 1]), this means we are in the descending part of the mountain. So, we move end to mid, as the peak could still be at mid.
- Otherwise, we move start to mid + 1, as the peak must be in the right part.
Termination:
- The loop terminates when start == end, and this index is the peak of the mountain.

⚡ Time Complexity:

The time complexity of this solution is O(log n), where n is the number of elements in the array. This is because we halve the search space in each step, as binary search does.

🎯 Key Takeaways:

The binary search technique is an efficient way to solve problems when you can leverage the sorted or partially sorted nature of the input.
Always think about how to reduce time complexity by avoiding brute-force solutions.
Practice problems like these to improve your algorithmic thinking!

Here’s a comprehensive note on essential Unix commands with examples

Mostafa Shariare — Fri, 13 Sep 2024 09:28:45 +0000

1. `pwd` – Print Working Directory

Displays the current directory you're working in.

   $ pwd
   /home/user

2. `ls` – List Directory Contents

Lists files and directories in the current directory.

   $ ls
   Documents Downloads Music Pictures

Options:

-l: Long listing format.
-a: Show hidden files.

   $ ls -la
   drwxr-xr-x  2 user user 4096 Sep 12 12:34 .
   drwxr-xr-x 25 user user 4096 Sep 11 13:14 ..
   -rw-r--r--  1 user user  220 Sep 12 11:32 .bashrc

3. `cd` – Change Directory

Navigates to a different directory.

   $ cd /home/user/Documents

To go back to the previous directory:

   $ cd -

4. `mkdir` – Make Directory

Creates a new directory.

   $ mkdir new_folder

5. `rmdir` – Remove Directory

Deletes an empty directory.

   $ rmdir old_folder

6. `rm` – Remove Files or Directories

Deletes files or directories.

   $ rm filename.txt

To remove a directory and its contents:

   $ rm -r directory_name

Force deletion without confirmation:

   $ rm -rf directory_name

7. `touch` – Create a New File

Creates an empty file.

   $ touch file.txt

8. `cp` – Copy Files or Directories

Copies files or directories.

   $ cp source.txt destination.txt

Copy directories recursively:

   $ cp -r source_directory/ destination_directory/

9. `mv` – Move (or Rename) Files or Directories

Moves or renames files or directories.

   $ mv oldname.txt newname.txt

To move a file to another directory:

   $ mv file.txt /path/to/directory/

10. `cat` – Concatenate and Display Files

Displays the content of a file.

   $ cat file.txt
   Hello, World!

Combine multiple files into one:

   $ cat file1.txt file2.txt > merged.txt

11. `more` and `less` – View File Content

more displays file content page by page.
```
 $ more file.txt
```
less allows scrolling through the file content with less memory usage.
```
 $ less file.txt
```

12. `head` and `tail` – Display File Content

head shows the first 10 lines by default.
```
 $ head file.txt
```
tail shows the last 10 lines.
```
 $ tail file.txt
```

Show specific number of lines:

   $ head -n 5 file.txt
   $ tail -n 5 file.txt

13. `find` – Search for Files and Directories

Searches files based on name, size, or other properties.

   $ find /path -name "filename.txt"

Find files based on size:

   $ find /path -size +100M

14. `grep` – Search Inside Files

Searches for a specific pattern within a file.

   $ grep "hello" file.txt

Search recursively in a directory:

   $ grep -r "pattern" /path/to/directory

15. `chmod` – Change File Permissions

Modify file permissions using symbolic (rwx) or numeric (777) notation.

   $ chmod 755 script.sh

Symbolic example:

   $ chmod u+x script.sh

16. `chown` – Change File Owner

Changes the ownership of files or directories.

   $ sudo chown user:group file.txt

17. `ps` – Process Status

Lists running processes.

   $ ps
   PID TTY          TIME CMD
   1234 pts/0    00:00:01 bash

Show all processes:

   $ ps aux

18. `kill` – Terminate Processes

Terminates a process using its PID (Process ID).

   $ kill 1234

Forcefully terminate:

   $ kill -9 1234

19. `top` – Real-Time Process Monitoring

Displays real-time information about system processes and resource usage.

   $ top

20. `df` – Disk Space Usage

Displays disk space usage of file systems.

   $ df -h
   Filesystem      Size  Used Avail Use% Mounted on
   /dev/sda1        50G   15G   32G  32% /

21. `du` – Disk Usage

Shows the disk usage of files and directories.

   $ du -sh *
   4.0K    file1.txt
   200M    folder

22. `tar` – Archive Files

Create or extract .tar archives.

   $ tar -cvf archive.tar file1 file2

Extract an archive:

   $ tar -xvf archive.tar

Compress with gzip:

   $ tar -czvf archive.tar.gz file1 file2

23. `zip` and `unzip` – Compress and Decompress Files

zip compresses files into a .zip archive.
```
 $ zip archive.zip file1 file2
```
unzip extracts files from a .zip archive.
```
 $ unzip archive.zip
```

24. `ssh` – Secure Shell

Connects to a remote server.

   $ ssh user@remote_server

25. `scp` – Secure Copy

Copies files between local and remote machines.

   $ scp file.txt user@remote:/path/to/destination/

26. `wget` – Download Files

Downloads files from the web.

   $ wget https://example.com/file.zip

27. `curl` – Transfer Data from a URL

Fetches content from a URL.

   $ curl https://example.com

28. `history` – View Command History

Shows previously executed commands.

   $ history

29. `alias` – Create Command Aliases

Creates a shortcut for a command.

   $ alias ll='ls -la'

30. `echo` – Display Text

Displays text or outputs data to a file.

   $ echo "Hello, World!"

Redirect output to a file:

   $ echo "Hello, World!" > file.txt

31. `man` – Manual Pages

Shows the manual or help pages for a command.

   $ man ls

32. `exit` – Exit the Terminal

Closes the terminal or ends the current session.

   $ exit

33. `sudo` – Execute Commands as Superuser

Runs commands with root privileges.

   $ sudo apt update

34. `apt` – Package Manager (For Debian-based systems)

Installs, updates, or removes software packages.

   $ sudo apt install package_name

35. `whoami` – Display Current User

Shows the username of the current user.

   $ whoami

Finding an Element in an Infinite Array Using Java

Mostafa Shariare — Wed, 11 Sep 2024 03:06:13 +0000

Problem Statement

Given an infinite array of sorted integers, we need to find the index of a given target number. The array is "infinite," meaning we cannot determine its size in advance, so we can't just apply a traditional binary search directly.

Approach Overview

Start with a small range: Initially, assume that the element lies within a small range (say, between indices 0 and 1).
Dynamically increase the range: If the target element is not found in the initial range, we double the size of the range to search further. This exponential growth allows us to quickly hone in on the range where the target might be located.
Binary search within the range: Once we determine a suitable range that contains the target, we apply binary search to efficiently find the target's index.

The Code

public class InfiniteArraySearch {
    public static void main(String[] args) {
        // Define the array (for demonstration purposes, treat this as infinite)
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};  
        int target = 6;

        // Call the function to find the target element
        int result = findElementInInfiniteArray(arr, target);
        System.out.println("Element found at index: " + result);
    }

    // Function to find the target in the infinite array
    static int findElementInInfiniteArray(int[] arr, int target) {
        // Start with a small range
        int start = 0;
        int end = 1;

        // Dynamically increase the range until the target is within bounds
        while (target > arr[end]) {
            int newStart = end + 1;  // Update start to one after the current end
            end = end + (end - start + 1) * 2;  // Double the range
            start = newStart;  // Move the start to newStart
        }

        // Perform binary search within the determined range
        return binarySearch(arr, target, start, end);
    }

    // Standard binary search implementation
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (target < arr[mid]) {
                end = mid - 1;  // Move the end to the left
            } else if (target > arr[mid]) {
                start = mid + 1;  // Move the start to the right
            } else {
                return mid;  // Element found
            }
        }
        return -1;  // Element not found
    }
}

Explanation of the Code

1. Main Function

The main function defines an example array arr and a target value 6. For simplicity, we assume the array is finite here, but conceptually, we treat it as infinite. The main function then calls findElementInInfiniteArray to search for the target, and prints the index if found.

2. Range Expansion (Linearly Expanding the Search Area)

In the findElementInInfiniteArray method:

We begin by assuming that the element lies within the range [0, 1].
If the target is greater than the value at arr[end], it means the target is not within the current range. So, we expand the range exponentially by doubling it (end = end + (end - start + 1) * 2). This effectively allows us to cover more ground in each iteration.

3. Binary Search

Once we know that the target must lie between start and end, we perform a standard binary search. Binary search is an efficient way to search in sorted arrays, as it reduces the search space by half at each step. The key comparisons are:

If the target is less than the middle element (arr[mid]), search the left half.
If the target is greater, search the right half.
If the target matches the middle element, return its index.

4. Edge Cases

If the target is smaller than the smallest element in the array, or if the array doesn't contain the target at all, the algorithm will return -1.

Time Complexity

Range Expansion: The range doubles with each iteration, so it takes O(log N) operations to find the right range where the target lies.
Binary Search: Once the range is found, binary search runs in O(log M), where M is the size of the range.

Thus, the overall time complexity is approximately O(log N + log M).

💡Solving LeetCode 34: Find First and Last Position of Element in a Sorted Array

Mostafa Shariare — Thu, 05 Sep 2024 17:32:01 +0000

Problem Statement

Given a sorted array of integers nums and a target value target, the task is to find the starting and ending position of the target in the array. If the target is not found in the array, return [-1, -1].

The problem asks for an efficient solution with a time complexity of O(log n), which hints at using binary search.

Example:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

In this example, the target 8 is found at positions 3 and 4.

Edge Case:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Here, the target 6 is not found in the array, so the output is [-1,-1].

Approach

The problem can be broken down into two main tasks:

Finding the leftmost (first) position of the target.
Finding the rightmost (last) position of the target.

Since the array is sorted, we can leverage binary search to efficiently find these positions. We will write two helper functions to achieve this:

findLeftBound(): This function will perform a binary search to find the first occurrence of the target.
findRightBound(): This function will perform a binary search to find the last occurrence of the target.

After finding both boundaries, we will return them in an array. If the target is not found in the array, both functions will return -1.

Solution Code

Here is the complete Java implementation of the solution:

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int[] nums = {5, 6, 7, 7, 7, 8, 9};
        int target = 7;

        int[] ans = searchRange(nums, target);
        System.out.println(Arrays.toString(ans));
    }

    public static int[] searchRange(int[] nums, int target) {
        int left = findLeftBound(nums, target);
        int right = findRightBound(nums, target);

        return new int[]{left, right};
    }

    static int findLeftBound(int[] nums, int target) {
        int index = -1;
        int start = 0;
        int end = nums.length - 1;

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

            if (nums[mid] == target) {
                index = mid;
                end = mid - 1;  // Move left to find the leftmost target
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return index;
    }

    static int findRightBound(int[] nums, int target) {
        int index = -1;
        int start = 0;
        int end = nums.length - 1;

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

            if (nums[mid] == target) {
                index = mid;
                start = mid + 1;  // Move right to find the rightmost target
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return index;
    }
}

Explanation

searchRange Function:
- This function is the main entry point for finding the range of the target. It calls two helper functions, findLeftBound and findRightBound, and returns their results in an array.
findLeftBound Function:
- The goal of this function is to find the first occurrence of the target.
- If nums[mid] equals target, we update index and move the end pointer to mid - 1 to continue searching on the left side.
- If nums[mid] is less than the target, we move the start pointer to mid + 1 to search the right side.
- If nums[mid] is greater than the target, we move the end pointer to mid - 1 to search the left side.
- This continues until start exceeds end.
findRightBound Function:
- The goal of this function is to find the last occurrence of the target.
- The logic is similar to findLeftBound, except that when we find the target, we move the start pointer to mid + 1 to continue searching on the right side.
Edge Cases:
- If the target is not found, both findLeftBound and findRightBound return -1, resulting in [-1, -1] being returned by searchRange.
- If the array is empty, both functions will return -1, which is handled properly.

Time Complexity

The time complexity of this solution is O(log n) for each of the helper functions due to the binary search. Since we call two binary searches, the total time complexity remains O(log n), which meets the problem's efficiency requirements.

Happy coding! 🚀

🤖 Solving LeetCode Problem 744: Find the Smallest Letter Greater Than Target

Mostafa Shariare — Thu, 05 Sep 2024 14:49:38 +0000

Problem Statement

Given a sorted array of characters letters containing only lowercase English letters, and a target letter target, find the smallest element in the array that is greater than the target. Note that the letters wrap around, meaning that if the target is greater than or equal to the largest letter in the array, the search should wrap around and return the smallest letter in the array.

Example 1:

Input: letters = ['c', 'f', 'j'], target = 'a'
Output: 'c'

Example 2:

Input: letters = ['c', 'f', 'j'], target = 'c'
Output: 'f'

Example 3:

Input: letters = ['c', 'f', 'j'], target = 'd'
Output: 'f'

Observations

The array is sorted, which makes binary search an ideal candidate for efficiently finding the result.
If the target is smaller than or equal to the smallest letter in the array, we should return that smallest letter.
If the target is larger than the largest letter in the array, we should return the first letter, because the array wraps around.

With these observations in mind, let's design our solution using binary search.

Approach

Binary search works by repeatedly dividing the search space in half. Here's how we'll apply it to this problem:

Initialize Variables: Start with two pointers, start at the beginning (0) and end at the end (letters.length - 1) of the array.
Binary Search:
- Calculate the middle index.
- If letters[mid] is greater than target, move the end pointer to mid - 1.
- If letters[mid] is less than or equal to target, move the start pointer to mid + 1.
Wrap Around: Once the binary search completes, the smallest letter greater than the target will be at the start index. If start exceeds the bounds of the array, use modulo operation to wrap around to the first letter in the array.
Return Result: Return the letter at the start % letters.length index.

Java Code Implementation

public class Solution {
    public static void main(String[] args) {

        char[] letters = {'c', 'f', 'j'};
        char target = 'a';

        char ans = nextGreatestLetter(letters, target);
        System.out.println(ans);
    }

    static char nextGreatestLetter(char[] letters, char target){

        int start = 0;
        int end = letters.length - 1;

        while (start <= end){

            int mid = start + (end - start) / 2;

            if (target >= letters[mid]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        // Since letters wrap around, we return letters[start % letters.length]
        return letters[start % letters.length];
    }
}

Explanation of the Code

Initialization:
- We start with start = 0 and end = letters.length - 1, which represent the beginning and end of the array.
Binary Search Logic:
- The condition if (target >= letters[mid]) moves the start pointer to mid + 1 when the target is greater than or equal to the middle element.
- Otherwise, we move the end pointer to mid - 1.
Handling Wrap Around:
- After the loop, the smallest letter greater than the target will be at the start index. If start is beyond the array's last index, we use start % letters.length to wrap around and access the first element.

Why Binary Search?

Binary search is ideal for this problem because:

Efficiency: The time complexity of binary search is O(log n), which is much faster than a linear scan (O(n)) for large arrays.
Sorted Array: The array is sorted, which is the prerequisite for applying binary search.

Edge Cases

Target Larger than Any Letter: If the target is greater than or equal to the last letter in the array, the search wraps around and returns the first letter.
Target Smaller than Smallest Letter: The binary search will find the smallest letter greater than the target.

🔎Finding Ceiling and Floor using Binary Search in Java (Handling Both Ascending and Descending Arrays)

Mostafa Shariare — Thu, 05 Sep 2024 05:46:35 +0000

Problem Statement

Given a sorted array arr and a target value target, implement two functions—one to find the ceiling and another to find the floor of the target in the array. The ceiling of a target is the smallest element that is greater than or equal to the target, and the floor is the largest element that is less than or equal to the target.

Additionally, the array can be either in ascending or descending order.

For example:

Input: arr = {2, 3, 5, 9, 14, 17, 18}, target = 15
Output: Floor = 14, Ceiling = 17

For descending order:

Input: arr = {18, 17, 14, 9, 5, 3, 2}, target = 15
Output: Floor = 14, Ceiling = 17

Approach

We'll use binary search to find the ceiling and floor of the target efficiently. The core idea is to identify whether the array is sorted in ascending or descending order and adjust our logic accordingly.

Ceiling: If the array is sorted in ascending order, we adjust the start pointer when the target is greater than the middle element. If the array is sorted in descending order, we adjust the end pointer instead.
Floor: The logic for the floor is similar but inverted. In ascending order, we adjust the end pointer when target is smaller than the middle element, and in descending order, we adjust the start pointer.

Code Implementation

Let's implement both functions, one for finding the ceiling and one for finding the floor. We will determine whether the array is in ascending or descending order and apply binary search accordingly.

public class CeilingAndFloor {

    // Function to find the ceiling of the target
    public static int ceiling(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;
        boolean isAscending = arr[start] < arr[end];  // Determine if the array is ascending

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

            if (arr[mid] == target) {
                return arr[mid];  // Target is found, return it as the ceiling
            }

            if (isAscending) {
                if (target < arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {  // If the array is in descending order
                if (target > arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
        }

        // If the loop ends, start will point to the smallest number greater than target (the ceiling)
        return arr[start];
    }

    // Function to find the floor of the target
    public static int floor(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;
        boolean isAscending = arr[start] < arr[end];  // Determine if the array is ascending

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

            if (arr[mid] == target) {
                return arr[mid];  // Target is found, return it as the floor
            }

            if (isAscending) {
                if (target < arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {  // If the array is in descending order
                if (target > arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
        }

        // If the loop ends, end will point to the largest number less than target (the floor)
        return arr[end];
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 9, 14, 17, 18};  // Ascending order array
        int target = 15;

        System.out.println("Ceiling: " + ceiling(arr, target));  // Output: 17
        System.out.println("Floor: " + floor(arr, target));  // Output: 14

        int[] arrDesc = {18, 17, 14, 9, 5, 3, 2};  // Descending order array
        System.out.println("Ceiling: " + ceiling(arrDesc, target));  // Output: 17
        System.out.println("Floor: " + floor(arrDesc, target));  // Output: 14
    }
}

Explanation

Initial Setup:
- We determine whether the array is in ascending or descending order by comparing the first and last elements of the array (arr[start] < arr[end]).
- Two functions, ceiling and floor, are implemented. Both use binary search but with slightly different logic based on whether the array is ascending or descending.
Binary Search Logic:
- For the ceiling:
  - If the array is ascending and the target is smaller than the middle element, we move end to mid - 1. If the target is larger, we move start to mid + 1.
  - In the case of a descending array, this logic is reversed.
- For the floor:
  - The same logic applies, but the roles of start and end are swapped.
Edge Cases:
- If the target is not found, the ceiling function returns arr[start] (the smallest element greater than or equal to the target) and the floor function returns arr[end] (the largest element less than or equal to the target).
Time Complexity: The binary search approach ensures that the solution runs in O(log n) time, making it efficient for large arrays.

Conclusion

By incorporating both ascending and descending order handling in our binary search approach, we've created a versatile solution for finding the ceiling and floor of a target value in any sorted array. This approach is not only efficient but also adaptable to different types of input arrays.

Understanding and mastering binary search problems like these is crucial for becoming proficient in coding interviews and competitive programming. Try experimenting with different inputs and arrays to solidify your understanding.

Happy coding! 🚀

java #binarysearch #datastructures #algorithms #competitiveprogramming #codinginterview #problemsolving #devto #programming #arrays

🚀 Why Choose Binary Search Over Linear Search?

Mostafa Shariare — Thu, 05 Sep 2024 00:39:41 +0000

When searching through a list, you might wonder why we sometimes prefer binary search over the simpler linear search. Here's a quick breakdown with a real-world example:

🔍 Linear Search:

How it works: Checks each element one by one.
Best use case: When the data is unsorted or small.
Time complexity: O(n) — as the list grows, the search time increases proportionally.

⚡ Binary Search:

How it works: Efficiently narrows down the search by repeatedly dividing the list in half.
Best use case: When the data is sorted.
Time complexity: O(log n) — even with large datasets, the search time grows slowly.

💡Example: Imagine you have an array with 2 million elements.

Linear Search: In the worst case, you might have to check every element, making it take up to 2 million steps.
Binary Search: Since binary search splits the list in half each time, it would only take about 21 steps (log₂(2,000,000) ≈ 21) to find the element, even in the worst case!

Happy coding! ✨

programming #algorithms #datastructures #binarysearch #linearsearch #optimization #tech

DEV Community: Mostafa Shariare

Building a Rotated Sorted Array Search in Java: Understanding Pivot and Binary Search

What is a Rotated Sorted Array?

The Search Strategy

Step-by-Step Code Explanation

Explanation of the Code

How the Algorithm Works

Conclusion

🚀 Solving LeetCode 852: Peak Index in a Mountain Array Using Binary Search

📝 Problem Statement:

🛠️ Approach:

🔨 Solution Code:

🔍 Explanation:

⚡ Time Complexity:

🎯 Key Takeaways:

Here’s a comprehensive note on essential Unix commands with examples

1. pwd – Print Working Directory

2. ls – List Directory Contents

3. cd – Change Directory

4. mkdir – Make Directory

5. rmdir – Remove Directory

6. rm – Remove Files or Directories

7. touch – Create a New File

8. cp – Copy Files or Directories

9. mv – Move (or Rename) Files or Directories

10. cat – Concatenate and Display Files

11. more and less – View File Content

12. head and tail – Display File Content

13. find – Search for Files and Directories

14. grep – Search Inside Files

15. chmod – Change File Permissions

16. chown – Change File Owner

17. ps – Process Status

18. kill – Terminate Processes

19. top – Real-Time Process Monitoring

20. df – Disk Space Usage

21. du – Disk Usage

22. tar – Archive Files

23. zip and unzip – Compress and Decompress Files

24. ssh – Secure Shell

25. scp – Secure Copy

26. wget – Download Files

27. curl – Transfer Data from a URL

28. history – View Command History

29. alias – Create Command Aliases

30. echo – Display Text

31. man – Manual Pages

32. exit – Exit the Terminal

33. sudo – Execute Commands as Superuser

34. apt – Package Manager (For Debian-based systems)

35. whoami – Display Current User

Finding an Element in an Infinite Array Using Java

Problem Statement

Approach Overview

The Code

Explanation of the Code

1. Main Function

2. Range Expansion (Linearly Expanding the Search Area)

3. Binary Search

4. Edge Cases

Time Complexity

💡Solving LeetCode 34: Find First and Last Position of Element in a Sorted Array

Problem Statement

Approach

Solution Code

Explanation

Time Complexity

🤖 Solving LeetCode Problem 744: Find the Smallest Letter Greater Than Target

Problem Statement

Observations

Approach

Java Code Implementation

Explanation of the Code

Why Binary Search?

Edge Cases

🔎Finding Ceiling and Floor using Binary Search in Java (Handling Both Ascending and Descending Arrays)

Problem Statement

Approach

Code Implementation

Explanation

1. `pwd` – Print Working Directory

2. `ls` – List Directory Contents

3. `cd` – Change Directory

4. `mkdir` – Make Directory

5. `rmdir` – Remove Directory

6. `rm` – Remove Files or Directories

7. `touch` – Create a New File

8. `cp` – Copy Files or Directories

9. `mv` – Move (or Rename) Files or Directories

10. `cat` – Concatenate and Display Files

11. `more` and `less` – View File Content

12. `head` and `tail` – Display File Content

13. `find` – Search for Files and Directories

14. `grep` – Search Inside Files

15. `chmod` – Change File Permissions

16. `chown` – Change File Owner

17. `ps` – Process Status

18. `kill` – Terminate Processes

19. `top` – Real-Time Process Monitoring

20. `df` – Disk Space Usage

21. `du` – Disk Usage

22. `tar` – Archive Files

23. `zip` and `unzip` – Compress and Decompress Files

24. `ssh` – Secure Shell

25. `scp` – Secure Copy

26. `wget` – Download Files

27. `curl` – Transfer Data from a URL

28. `history` – View Command History

29. `alias` – Create Command Aliases

30. `echo` – Display Text

31. `man` – Manual Pages

32. `exit` – Exit the Terminal

33. `sudo` – Execute Commands as Superuser

34. `apt` – Package Manager (For Debian-based systems)

35. `whoami` – Display Current User