Search in Bitonic Array - Java Solution

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

1. Introduction

In this blog post, we'll explore a method to search for a target value in a bitonic array. A bitonic array is an array that first increases and then decreases. The goal is to find the index of a target value in O(log n) time using a modified binary search approach.

Problem

Given a bitonic array of numbers and a target value, find the index of the target in the array.

2. Solution Steps

1. Find the peak element (maximum value) in the bitonic array using binary search.

2. Perform binary search on the increasing part of the array to find the target.

3. Perform binary search on the decreasing part of the array to find the target.

4. If the target is found in either part, return its index. Otherwise, return -1.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] arr1 = {2, 4, 8, 10, 7, 6, 1};
        System.out.println("Index of 6: " + searchBitonic(arr1, 6));

        int[] arr2 = {2, 4, 6, 8, 10, 5, 3, 1};
        System.out.println("Index of 30: " + searchBitonic(arr2, 30));
    }

    // Method to search in a bitonic array
    public static int searchBitonic(int[] arr, int target) {
        int peak = findPeak(arr);
        int index = binarySearch(arr, 0, peak, target, true);
        if (index != -1) {
            return index;
        }
        return binarySearch(arr, peak + 1, arr.length - 1, target, false);
    }

    // Helper method to find the peak element in a bitonic array
    private static int findPeak(int[] arr) {
        int start = 0, end = arr.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (arr[mid] > arr[mid + 1]) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    // Standard binary search algorithm, modified to work with both increasing and decreasing parts
    private static int binarySearch(int[] arr, int start, int end, int target, boolean isAscending) {
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (arr[mid] == target) {
                return mid;
            }

            if (isAscending) {
                if (target < arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if (target > arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
        }
        return -1;
    }
}

Output:

Index of 6: 5
Index of 30: -1

Explanation:

The searchBitonic method first finds the peak of the bitonic array. It then performs a binary search on the increasing and decreasing parts of the array to find the target value. 

For example, in the array {2, 4, 8, 10, 7, 6, 1}, the peak is at index 3 (value 10). 

For target 6, the method searches the decreasing part and finds 6 at index 5. 

For target 30, it returns -1 as the target is not found in the array.

My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:

Build REST APIs with Spring Boot 4, Spring Security 7, and JWT

🆕 High-Demand 80–90% OFF

[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25

🆕 High-Demand 80–90% OFF

ChatGPT + Generative AI + Prompt Engineering for Beginners

🚀 Trending Now 80–90% OFF

Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Real-Time REST APIs with Spring Boot - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Microservices with Spring Boot and Spring Cloud

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Java Full-Stack Developer Course with Spring Boot and React JS

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Build 5 Spring Boot Projects with Java: Line-by-Line Coding

🌟 Top Rated 80–90% OFF

Testing Spring Boot Application with JUnit and Mockito

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot Thymeleaf Real-Time Web Application - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Master Spring Data JPA with Hibernate

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot + Apache Kafka Course - The Practical Guide

🎓 Student Favorite 80–90% OFF
Available in Udemy for Business

Java Testing: Mastering JUnit 5 Framework

🆕 New 80–90% OFF

Reactive Programming in Java: Spring WebFlux and Testing

🌟 Top Rated 80–90% OFF

Spring Boot + RabbitMQ Course - The Practical Guide

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Functional Programming in Java (Includes Java Collections)

🎓 Student Favorite 80–90% OFF

ChatGPT for Java Developers: Boost Your Productivity with AI

🚀 Trending Now 80–90% OFF