Binary Search and Problems

# Binary Search and Its Applications

## Introduction
- Explanation of what binary search is, its principle, and code.
- In this video, we will discuss binary search problems.

## First Question: Find the First and Last Position of an Element in a Sorted Array
- Question: Find the first and last position of an element (key) in a sorted array.
- Example: array = [0, 1, 2, 3, 4, 5, 6, 7]
- If you need to find the position of 3:
  - Return -1 if the element is not found.
  - Return its index if the element is found.

### Input and Output Format
- Input:
  - First line: the number of test cases
  - Second line: size of the array and value of the key
- Output:
  - Indices of the first and last occurrence or -1.

### Using Binary Search
- Find the first and last occurrence using binary search.
- Three main conditions:
  1. If arr[mid] == key, store the answer and set end to mid - 1.
  2. If arr[mid] > key, set end to mid - 1.
  3. If arr[mid] < key, set start to mid + 1.

## Second Question: Peak Index in a Mountain Array
- Question: Find the position of the peak element in a mountain array.
- Meaning of mountain array: first increases and then decreases.
- Example: array = [0, 2, 1, 0] (peak is 2)

### Using Binary Search
- Use binary search to find the peak element.
- Conditions:
  1. If arr[mid] < arr[mid + 1], set start to mid + 1.
  2. Otherwise, set end to mid.
- Continue until start == end.

## Conclusion
- By using binary search, we can find the first and last occurrences and the position of the peak element in a mountain array.
- In the next video, we will discuss more problems.