Introduction

The Binary Search algorithm is an efficient searching technique used on sorted arrays.

Given a sorted array arr[] and a target element x, the task is to find the index of the target element.

Binary Search works by:

  • repeatedly dividing the search space into half
  • comparing the middle element with target
  • eliminating unnecessary portions of the array

This problem helps in understanding:

  • divide and conquer
  • efficient searching
  • pointer manipulation
  • logarithmic optimization

Example

Input: arr[] = [1,3,5,7,9,11]x = 7
Output: 3
Explanation:
Element 7 is present at index 3.

Input: arr[] = [2,4,6,8,10]
x = 5
Output: -1
Explanation:
Element 5 does not exist in the array.

Constraints

 1 <= n <= 10^5 -10^9 <= arr[i] <= 10^9 -10^9 <= x <= 10^9   Array is sorted

Approach 1 : Brute Force (Linear Search)

Explanation

The simplest way to solve this problem is:

  1. Traverse the array sequentially
  2. Compare every element with target
  3. Return index if found

This approach works but does not utilize the sorted property of the array.

Steps

  1. Traverse the array.
  2. Compare current element with target.
  3. If found:
    • return index
  4. Otherwise:
    • continue traversal
  5. Return -1 if target not found.

Dry Run

Input Array:[1,3,5,7,9,11]
Target = 7

Traverse 1:
1 != 7

Traverse 3:
3 != 7

Traverse 5:
5 != 7

Traverse 7:
7 == 7
Element found at index 3
Return 3

Brute Force Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Every element may need to be checked.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Approach 2 : Optimized Solution (Binary Search)

Explanation

Since the array is sorted, we can use Binary Search.

The idea is:

  1. Find middle element
  2. Compare middle element with target
  3. If:
    • middle == target:
      • return index
    • target < middle:
      • search left half
    • target > middle:
      • search right half

This repeatedly reduces the search space by half.

Steps

  1. Initialize:
    • left = 0
    • right = n - 1
  2. While left ≤ right:
    • find middle index
  3. Compare middle element with target.
  4. If target smaller:
    • move right pointer
  5. If target greater:
    • move left pointer
  6. Return index if found.
  7. Otherwise return -1.

Dry Run

Input Array:[1,3,5,7,9,11]
Target = 7

Initially:
left = 0
right = 5
Middle = 2
arr[2] = 5
5 < 7

Move left pointer
left = 3
right = 5
Middle = 4
arr[4] = 9
9 > 7

Move right pointer
right = 3
Middle = 3
arr[3] = 7

Target found
Return 3

Optimized Code

Complexity Analysis

Time Complexity: O(log n)Explanation:
Search space is reduced by half in every iteration

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Edge Cases

  1. Element present at beginning
  2. Element present at end
  3. Element not present
  4. Array contains one element
  5. Large sorted arrays

Why This Problem is Important

This problem helps in understanding:

  1. Divide and conquer
  2. Logarithmic optimization
  3. Efficient searching
  4. Pointer manipulation
  5. Sorted array processing

It is one of the most important searching interview problems.

Real-World Applications

Binary Search is used in:

  1. Database indexing
  2. Search engines
  3. Dictionary lookup
  4. Operating systems
  5. Large-scale data retrieval

Common Mistakes

  1. Incorrect middle calculation
  2. Infinite loop conditions
  3. Wrong pointer updates
  4. Forgetting sorted array requirement

Interview Tips

Interviewers often expect:

  1. O(log n) Binary Search
  2. Proper pointer updates
  3. Middle element explanation

Always explain how Binary Search reduces search space efficiently.

Related Questions

  1. Search Insert Position
  2. First Occurrence
  3. Last Occurrence
  4. Peak Element
  5. Rotated Sorted Array Search

Final Takeaway

Binary Search is one of the most important searching algorithms that teaches divide-and-conquer optimization and logarithmic searching techniques. Understanding this problem builds a strong foundation for advanced searching and optimization interview problems.