CODEWITHSUNDEEP
algorithmbinary-search
Aswin Prasad
Aswin Prasad

Reputation: 417

Binay search for maximum element in bitonic sequence

First, a bitonic array for this question is defined as one such that for some index K in an array of length N where 0 < K < N - 1 and 0 to K is a monotonically increasing sequence of integers, and K to N - 1 is a monotonically decreasing sequence of integers.

Example: [1, 3, 4, 6, 9, 14, 11, 7, 2, -4, -9]. It monotonically increases from 1 to 14, then decreases from 14 to -9.

My concern is I can't understand the binary search for finding the largest element in the bitonic sequence.

Upvotes: 1

Views: 1046

Answers (2)

PlsWork
PlsWork

Reputation: 2158

Returns the index of the largest element in a given bitonic array (first ascending, then descending, no duplicates):

private int findMax(int[] array, int low, int high) {
    int mid = low + (high-low)/2;

    if (high == low) return high;   // max has be found

    else if (array[mid] < array[mid+1]) {
        return findMax(array, ++mid, high); // search in the right subarray
    } else {
        return findMax(array, low, mid);    // search in the left subarray
    }
}

Upvotes: 0

Ami Tavory
Ami Tavory

Reputation: 76297

You're basically searching for position m such that the items increase up to m, and decrease starting from it.

A modification of the regular binary search can solve this.

Your search proceeds at each iteration between l and r, initialized to 0 and n - 1, respectively.

At each iteration, choose m = ⌊(l + r) / 2⌋. Check the left and right neighbors of m (except if m = 0 or m = n - 1, where you check only one neighbor), and compare the three elements. There are three cases:

  1. The left neighbor is smaller and the right neighbor is smaller - the element at m is the one you want.

  2. The left neighbor is smaller and the right neighbor is larger - you need to search to the right.

  3. The left neighbor is larger and the right neighbor is smaller - you need to search to the left.

When you move to the left or right, you adjust l and r as in the usual binary search.

Termination is as in the regular binary search as well, except for the following. Note that if it terminates at a point where you didn't find a lower right neighbor, the answer is at n - 1; if it terminates with finding a lower left neighbor, the answer is at 0.

Upvotes: 4

Related Questions