DSA
brian | Published: March 12, 2024, 5:25 p.m. | Updated: July 12, 2025, 9:58 a.m.
Binary Search:
1.ordered array, almost identical to regular arrays but ordered arrays require that the values are ordered. Every time a value gets added, it will be sorted into appropriate cell.
2.in ordered array we have to check cell one by one, and compare if the value being inserted is less or greater.. if its greater then we have to keep going to the right until we have a match..
3. after we have a match we have to move all cells to the right(example if its in the middle)
4. not efficient in inserting, but searching it is more efficient
[3, 17, 75, 80, 202] -lets say we were searching for 22, we can stop the search at 75 before we even look through all the elements because the array is sorted, so we know
that were not going to find 22 anymore
5. ordered array allows for binary search
Binary search is an efficient algorithm with a time complexity of O(log n), where n is the number of elements in the sorted array. This is significantly faster than linear search, which has a time complexity of O(n), especially for large datasets. However,
binary search requires the input array to be sorted beforehand.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]---->lets say the number were looking for is 4
*we start off in the middle(5)
*pc says lower so we go middle again(3)
*pc says higher so we say 4 and we get the answer...
Binary search vs Linear Searh:
array containing 100 values
Linear Search: maximum search: 100 steps
Binary Search: maximum search: 7 steps
*if we double the steps, just increase 1 step for the steps in binary 200 values ---> 8 steps..... 400 values 9 steps.... 800 values 10 steps