Page 1 of 1
a 1. We know we can do binary search on a sorted array A[1.1) in (log n) time. But what if we don't know the value n? Yo
Posted: Sun May 15, 2022 11:51 am
by answerhappygod
- A 1 We Know We Can Do Binary Search On A Sorted Array A 1 1 In Log N Time But What If We Don T Know The Value N Yo 1 (37.5 KiB) Viewed 53 times
a 1. We know we can do binary search on a sorted array A[1.1) in (log n) time. But what if we don't know the value n? Your task in this problem is to give (log n)-time algorithm to search such an array for a target t, returning the index in A of t, if it exists, or else -1. (You can assume for simplicity that the values of A are all distinct.) Since you don't know A's length, a common occurrence will be falling of the end of A. i.e., trying to access Alil for an i greater than the unknown value of) n. In programming doing this might return an error or throw an exception. For the purposes of this problem, it may be simpler to assume that A
will evaluate to "0" whenever i>n, ie, a comparison between A[n + 1) and other actual value (either the target t or any A for 1 Sin will always say Aſn + 1) is larger. Alternatively, you can assume you're allowed to write if statements with tests such as: if (A = ""): ... Exanple: if A = 14.7. 10.45] (in which case n = 4), then A[4] will correctly give 45, but 45 will give", as will A(6), A7), etc.