concept · INFO-CS-ADS-119Binary Search on Sorted Arrays
Binary search on sorted arrays uses the ordering of array elements to determine which half of the array can contain a target, allowing efficient lookups and boundary searches.
Explanation
Overview
Binary search on sorted arrays is the application of binary search to an array whose elements are arranged in ascending or descending order. The algorithm uses indexed access to inspect the middle element of a search interval.
Purpose
It provides efficient element lookup in ordered arrays and supports related operations such as finding insertion positions, lower bounds, upper bounds, and ranges of duplicate values.
Key concepts
name: Core idea; description: The central focus of binary search on sorted arrays is the capability described here: Binary search on sorted arrays uses the ordering of array elements to determine which half of the array can contain a target, allowing efficient lookups and boundary searches.; name: Problem context; description: Binary Search on Sorted Arrays is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using binary search on sorted arrays, check its assumptions, input requirements, expected output, and resource constraints.
Time complexity
O(log n) time for locating a target or a boundary because the candidate interval is approximately halved at each iteration.
Space complexity
O(1) auxiliary space for an iterative implementation, excluding the storage occupied by the original array.
Example
For the ascending array [4, 9, 13, 18, 24, 29, 35, 42], searching for 29 begins at the middle element 18. The search moves right, examines 29, and returns its index 5.
Pseudocode
BINARY_SEARCH_SORTED(A, target):
low = 0
high = length(A) - 1
while low <= high:
mid = low + (high - low) // 2
if A[mid] == target:
return mid
if A[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Example or application
For the ascending array [4, 9, 13, 18, 24, 29, 35, 42], searching for 29 begins at the middle element 18. The search moves right, examines 29, and returns its index 5.
Definition
Binary search on sorted arrays is the application of binary search to an array whose elements are arranged in ascending or descending order. The algorithm uses indexed access to inspect the middle element of a search interval.
Purpose
It provides efficient element lookup in ordered arrays and supports related operations such as finding insertion positions, lower bounds, upper bounds, and ranges of duplicate values.
Sorted Order
The array must follow a consistent ordering. An ascending array places smaller values before larger values, while a descending array places larger values before smaller values.
Array Indexing
An array provides direct access to an element at a specified index. This allows the algorithm to examine the middle element in O(1) time without traversing all preceding elements.
Search Boundaries
The low and high variables define the current candidate interval. In an inclusive implementation, both boundaries refer to valid array positions.
Middle Element
The middle index divides the current interval into left and right sections. Its value determines which section can still contain the target.
Ascending Array Logic
For an ascending array, if the middle value is smaller than the target, the target can only be in the right portion. If the middle value is larger, the target can only be in the left portion.
Descending Array Logic
For a descending array, the direction of the comparison is reversed. If the middle value is smaller than the target, the search continues toward the left; if it is larger, the search continues toward the right.
Pseudocode
BINARY_SEARCH_SORTED(A, target):
low = 0
high = length(A) - 1
while low <= high:
mid = low + (high - low) // 2
if A[mid] == target:
return mid
if A[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Lower Bound
The lower bound is the first index at which an element is greater than or equal to a target in an ascending array. It can be found with a modified binary search that continues narrowing the interval after finding a qualifying element.
Upper Bound
The upper bound is the first index at which an element is strictly greater than the target in an ascending array. The difference between upper bound and lower bound gives the number of occurrences of the target.
Insertion Position
A lower-bound-style binary search can identify the position where a new element should be inserted while preserving sorted order. Inserting into an array may still require shifting later elements, which takes O(n) time.
Duplicate Handling
A standard search may return any matching duplicate. Boundary-based variants can locate the first occurrence, last occurrence, or complete range of matching values.
Time Complexity
O(log n) time for locating a target or a boundary because the candidate interval is approximately halved at each iteration.
Space Complexity
O(1) auxiliary space for an iterative implementation, excluding the storage occupied by the original array.
Sorting Cost
If the array is initially unsorted, sorting it first generally takes O(n log n) time with an efficient comparison-based sorting algorithm. Binary search is especially useful when the sorted array is searched repeatedly.
Advantages
Fast lookup in large sorted arrays.
Efficiently locates boundary positions.
Supports range queries and duplicate counting.
Uses little additional memory in its iterative form.
Works well with arrays that remain unchanged between searches.
Limitations
Incorrectly sorted data can produce incorrect results.
Maintaining sorted order can be expensive when many insertions and deletions occur.
Middle-index access is not constant-time in ordinary linked lists.
Duplicate-related requirements need specialized boundary logic.
Practical Applications
Searching sorted student or employee records.
Finding a product price in an ordered array.
Locating a value in a sorted numerical dataset.
Finding insertion positions in ordered collections.
Counting repeated values in sorted data.
Implementation Considerations
The implementation must match its comparison direction to the array's ordering. It should also define whether the search returns any occurrence, the first occurrence, the last occurrence, or an insertion position.
Key Takeaway
Sorted arrays are particularly suitable for binary search because they combine ordering information with constant-time indexed access. The same technique can also solve boundary and insertion-position problems.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of binary search on sorted arrays is the capability described here: Binary search on sorted arrays uses the ordering of array elements to determine which half of the array can contain a target, allowing efficient lookups and boundary searches. |
Problem context | Binary Search on Sorted Arrays is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using binary search on sorted arrays, check its assumptions, input requirements, expected output, and resource constraints. |
Practice Questions
| Question | Answer |
|---|
What is the main purpose of binary search on sorted arrays? | Binary search on sorted arrays uses the ordering of array elements to determine which half of the array can contain a target, allowing efficient lookups and boundary searches. |
What should be checked before applying binary search on sorted arrays? | For binary search on sorted arrays, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of binary search on sorted arrays be validated? | Trace a representative binary search on sorted arrays case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of binary search on sorted arrays.
Identify the assumptions, inputs, and conditions relevant to binary search on sorted arrays.
Evaluate an application of binary search on sorted arrays for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures