Binary Search Algorithm O log n Search is an important DAA topic because it appears in real projects, debugging sessions, and interviews. Learn the meaning first, then connect it to a small working example so the rule does not stay abstract.
For this page, focus on what problem Binary Search Algorithm O log n Search solves, where developers usually make mistakes, and how to verify the result. The audit note for this lesson was: limited checklist/practice/mistake/FAQ notes .
A strong understanding of Binary Search Algorithm O log n Search should include syntax, behavior, one realistic use case, one failure case, and one quick way to check your work with tools or output.
Binary Search Algorithm O log n Search should be studied as a practical algorithm analysis lesson, not as a label. Start by naming the input, the rule that changes the input, and the result a learner should be able to predict after reading the page.
In the daa > binary-search page, the notes should connect the definition with a working scenario, a mistake that beginners actually make, and the exact check that proves the fix. That makes the topic useful for coding, debugging, and interview revision.
Binary Search is an efficient searching algorithm used to find an element in a sorted array or sorted list. Instead of checking every element one by one, it repeatedly cuts the search space into two halves.
Because half of the remaining elements are discarded at every step, binary search is much faster than linear search for large sorted data sets.
The strength of binary search comes from elimination. After one comparison, half of the remaining elements are ignored. After another comparison, half of what remains is ignored again.
For example, if an array has 1,024 elements:
That is why binary search has logarithmic time complexity.
Binary search works correctly only when the data is sorted.
At each step:
This is a classic divide and conquer algorithm because each step reduces the problem from size n to roughly n / 2.
| Case | Complexity | Reason |
|---|---|---|
| Best case | O(1) | Target is found at the first middle check |
| Average case | O(log n) | Search space is halved repeatedly |
| Worst case | O(log n) | Need to reduce the interval until empty |
| Iterative space | O(1) | Uses only a few variables |
| Recursive space | O(log n) | Uses call stack for recursive calls |
The iterative version is usually preferred because it is simple and uses constant extra space.
public class BinarySearchIterative {
static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}The recursive version expresses the divide-and-conquer idea more directly, but it uses extra stack space.
public class BinarySearchRecursive {
static int binarySearch(int[] arr, int low, int high, int target) {
if (low > high) {
return -1;
}
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
return binarySearch(arr, mid + 1, high, target);
}
return binarySearch(arr, low, mid - 1, target);
}
}Instead of writing (low + high) / 2, many implementations use:
mid = low + (high - low) / 2
This avoids possible integer overflow when low + high becomes too large.
When solving binary search questions by hand, follow this order:
Suppose:
arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19} and target = 7
| Step | low | high | mid | arr[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 9 | Search left half |
| 2 | 0 | 3 | 1 | 3 | Search right half |
| 3 | 2 | 3 | 2 | 5 | Search right half |
| 4 | 3 | 3 | 3 | 7 | Found |
Binary search ends when low becomes greater than high. This means there is no valid search interval left, so the target does not exist in the array.
This stopping condition is very important. Without it, the loop or recursion may continue incorrectly.
Binary search is not limited to exact search. Many common interview and algorithm problems are based on its variants.
| Variant | Goal | Main Idea |
|---|---|---|
| First occurrence | Find the leftmost index of target | When found, continue searching left |
| Last occurrence | Find the rightmost index of target | When found, continue searching right |
| Count occurrences | Count duplicates | Use first and last occurrence |
| Floor | Largest value less than or equal to target | Track best smaller value |
| Ceiling | Smallest value greater than or equal to target | Track best larger value |
| Rotated sorted array search | Find value in rotated array | Identify which half is sorted |
| Binary search on answer | Search over possible answers | Use a monotonic condition |
When duplicates are present, normal binary search may return any matching index. To find the first or last occurrence, continue the search even after a match is found.
public class BinarySearchOccurrences {
static int firstOccurrence(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid;
high = mid - 1;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
static int lastOccurrence(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid;
low = mid + 1;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
}Sometimes we do not search for an array element at all. Instead, we search over a range of possible answers. This works when the condition is monotonic, meaning that once a certain value works, all larger values also work, or all smaller values also work.
public class SqrtBinarySearch {
static long sqrt(long n) {
if (n < 2) {
return n;
}
long low = 1;
long high = n / 2;
long result = 1;
while (low <= high) {
long mid = low + (high - low) / 2;
if (mid * mid == n) {
return mid;
}
if (mid * mid < n) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
}| Aspect | Binary Search | Linear Search |
|---|---|---|
| Data requirement | Needs sorted data | Works on any data |
| Time complexity | O(log n) | O(n) |
| Best use case | Large sorted collections | Small or unsorted collections |
| Implementation | Slightly more careful | Very simple |
1. Define the input for Binary Search Algorithm O log n Search.
2. Apply the rule from the lesson.
3. Compare the actual result with the expected result.
4. Record the fix if the result differs.1. Try empty, missing, duplicate, or invalid data.
2. Identify where Binary Search Algorithm O log n Search changes behavior.
3. Explain the safest correction.
4. Retest the normal path.Memorizing Binary Search Algorithm O log n Search without the situation where it is useful.
Connect Binary Search Algorithm O log n Search to a concrete algorithm analysis task.
Testing Binary Search Algorithm O log n Search only with the perfect input.
Include empty, missing, duplicate, incompatible, or failed cases when relevant.
Changing code before reading the visible symptom or error message.
Inspect the output, state, configuration, or stack trace connected to Binary Search Algorithm O log n Search.
Memorizing Binary Search Algorithm O log n Search without the situation where it is useful.
Connect Binary Search Algorithm O log n Search to a concrete algorithm analysis task.
The common mistake is memorizing syntax without understanding when the behavior changes or fails.
Remember the problem it solves in algorithm analysis, then attach the syntax or steps to that problem.
You can predict the result of a small example, explain a failure case, and choose it over a nearby alternative for a clear reason.
They often copy the syntax but skip the state, input, dependency, selector, route, type, or configuration that controls the behavior.
Explore 500+ free tutorials across 20+ languages and frameworks.