Search in Bitonic Array - Java Solution

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.