Problem

Given a bitonic array of numbers and a target value, find the index of the target value in the bitonic array in O(log n) time.

A bitonic array is an array that is first strictly increasing and then strictly decreasing.

Examples

Example 1

1
2
3

Input: arr = [2, 4, 8, 10, 7, 6, 1], target = 6
Output: 5
Explanation: 6 is found at index 5.

Example 2

1
2
3

Input: arr = [2, 4, 6, 8, 10, 5, 3, 1], target = 30
Output: -1
Explanation: 30 is not found in the array.
Similar Problems

Solution

Method 1 – Bitonic Binary Search

This problem is closely related to:

Intuition

The key idea is to first find the peak (maximum) element in the bitonic array. The left part is strictly increasing, and the right part is strictly decreasing. We can then apply binary search on both sides: a standard binary search on the increasing part, and a reverse binary search on the decreasing part.

Approach

  1. Find the peak (maximum) element index using binary search.
  2. Apply binary search on the left (increasing) part from index 0 to peak.
  3. Apply binary search on the right (decreasing) part from peak+1 to end.
  4. Return the index if found, else -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
  int searchBitonic(const std::vector<int>& arr, int target) {
    int peak = findPeak(arr);
    int idx = binarySearch(arr, 0, peak, target, true);
    if (idx != -1) return idx;
    return binarySearch(arr, peak + 1, arr.size() - 1, target, false);
  }
private:
  int findPeak(const std::vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
      int mid = left + (right - left) / 2;
      if (arr[mid] < arr[mid + 1]) left = mid + 1;
      else right = mid;
    }
    return left;
  }
  int binarySearch(const std::vector<int>& arr, int left, int right, int target, bool asc) {
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (arr[mid] == target) return mid;
      if (asc) {
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
      } else {
        if (arr[mid] > target) left = mid + 1;
        else right = mid - 1;
      }
    }
    return -1;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

func SearchBitonic(arr []int, target int) int {
  peak := findPeak(arr)
  idx := binarySearch(arr, 0, peak, target, true)
  if idx != -1 {
    return idx
  }
  return binarySearch(arr, peak+1, len(arr)-1, target, false)
}

func findPeak(arr []int) int {
  left, right := 0, len(arr)-1
  for left < right {
    mid := left + (right-left)/2
    if arr[mid] < arr[mid+1] {
      left = mid + 1
    } else {
      right = mid
    }
  }
  return left
}

func binarySearch(arr []int, left, right, target int, asc bool) int {
  for left <= right {
    mid := left + (right-left)/2
    if arr[mid] == target {
      return mid
    }
    if asc {
      if arr[mid] < target {
        left = mid + 1
      } else {
        right = mid - 1
      }
    } else {
      if arr[mid] > target {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
  }
  return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
  public int searchBitonic(int[] arr, int target) {
    int peak = findPeak(arr);
    int idx = binarySearch(arr, 0, peak, target, true);
    if (idx != -1) return idx;
    return binarySearch(arr, peak + 1, arr.length - 1, target, false);
  }
  private int findPeak(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
      int mid = left + (right - left) / 2;
      if (arr[mid] < arr[mid + 1]) left = mid + 1;
      else right = mid;
    }
    return left;
  }
  private int binarySearch(int[] arr, int left, int right, int target, boolean asc) {
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (arr[mid] == target) return mid;
      if (asc) {
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
      } else {
        if (arr[mid] > target) left = mid + 1;
        else right = mid - 1;
      }
    }
    return -1;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
  fun searchBitonic(arr: IntArray, target: Int): Int {
    val peak = findPeak(arr)
    val idx = binarySearch(arr, 0, peak, target, true)
    if (idx != -1) return idx
    return binarySearch(arr, peak + 1, arr.size - 1, target, false)
  }
  private fun findPeak(arr: IntArray): Int {
    var left = 0; var right = arr.size - 1
    while (left < right) {
      val mid = left + (right - left) / 2
      if (arr[mid] < arr[mid + 1]) left = mid + 1
      else right = mid
    }
    return left
  }
  private fun binarySearch(arr: IntArray, left: Int, right: Int, target: Int, asc: Boolean): Int {
    var l = left; var r = right
    while (l <= r) {
      val mid = l + (r - l) / 2
      if (arr[mid] == target) return mid
      if (asc) {
        if (arr[mid] < target) l = mid + 1
        else r = mid - 1
      } else {
        if (arr[mid] > target) l = mid + 1
        else r = mid - 1
      }
    }
    return -1
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
  def search_bitonic(self, arr: list[int], target: int) -> int:
    def find_peak(arr):
      left, right = 0, len(arr) - 1
      while left < right:
        mid = (left + right) // 2
        if arr[mid] < arr[mid + 1]:
          left = mid + 1
        else:
          right = mid
      return left
    def binary_search(arr, left, right, target, asc):
      while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
          return mid
        if asc:
          if arr[mid] < target:
            left = mid + 1
          else:
            right = mid - 1
        else:
          if arr[mid] > target:
            left = mid + 1
          else:
            right = mid - 1
      return -1
    peak = find_peak(arr)
    idx = binary_search(arr, 0, peak, target, True)
    if idx != -1:
      return idx
    return binary_search(arr, peak + 1, len(arr) - 1, target, False)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

impl Solution {
  pub fn search_bitonic(arr: &[i32], target: i32) -> i32 {
    fn find_peak(arr: &[i32]) -> usize {
      let (mut left, mut right) = (0, arr.len() - 1);
      while left < right {
        let mid = left + (right - left) / 2;
        if arr[mid] < arr[mid + 1] {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      left
    }
    fn binary_search(arr: &[i32], left: usize, right: usize, target: i32, asc: bool) -> i32 {
      let (mut l, mut r) = (left, right);
      while l <= r {
        let mid = l + (r - l) / 2;
        if arr[mid] == target {
          return mid as i32;
        }
        if asc {
          if arr[mid] < target {
            l = mid + 1;
          } else {
            r = mid - 1;
          }
        } else {
          if arr[mid] > target {
            l = mid + 1;
          } else {
            r = mid - 1;
          }
        }
      }
      -1
    }
    let peak = find_peak(arr);
    let idx = binary_search(arr, 0, peak, target, true);
    if idx != -1 {
      return idx;
    }
    binary_search(arr, peak + 1, arr.len() - 1, target, false)
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
  searchBitonic(arr: number[], target: number): number {
    const peak = this.findPeak(arr);
    let idx = this.binarySearch(arr, 0, peak, target, true);
    if (idx !== -1) return idx;
    return this.binarySearch(arr, peak + 1, arr.length - 1, target, false);
  }
  private findPeak(arr: number[]): number {
    let left = 0, right = arr.length - 1;
    while (left < right) {
      const mid = left + Math.floor((right - left) / 2);
      if (arr[mid] < arr[mid + 1]) left = mid + 1;
      else right = mid;
    }
    return left;
  }
  private binarySearch(arr: number[], left: number, right: number, target: number, asc: boolean): number {
    while (left <= right) {
      const mid = left + Math.floor((right - left) / 2);
      if (arr[mid] === target) return mid;
      if (asc) {
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
      } else {
        if (arr[mid] > target) left = mid + 1;
        else right = mid - 1;
      }
    }
    return -1;
  }
}

Complexity

  • ⏰ Time complexity: O(log n) — Each binary search and peak finding runs in logarithmic time.
  • 🧺 Space complexity: O(1) — Only a constant number of variables are used.